<<개발일지>>

이 문제는 계단 오르기와 크게 다를게 없는 문제이다. 다만, 상황상 어디까지 계산해야하는지가 중요한 것이다. 7번째 돌까지 갔다고 해서 다 건넜다는 것은 잘못된 생각이다. 그 부분만 조심한다면 dp 풀이 방법으로 쉽게 접근해서 풀 수 있는 문제이다. (아직까지 안 익숙하다는 뜻이겟네 ㅋㅋ ) 홧팅 import java.util.Scanner; class Main { public static int[] dy; private int solution(int n) { dy[1] = 1; dy[2] = 2; for (int i = 3; i

이 문제는 Greedy 라는 방식을 채택하여 푸는 문제이다. 이를 생각하지 않고 접근 한다면 생각보다 복잡한 형태로 코드가 구성이 되고 자칫 시간 복잡도가 N^2가 되므로 시간 초과가가 발생한다. 그렇기 때문에 Greedy의 의미인 여기서는 키를 내림차순으로 만듦으로써 몸무게만 비교하면 되는 형태로 최적화 시켰다. 키를 정렬하기 위해서 객체를 정렬해야 하는데, Comparable와 compareTo() 를 이용해서 구했다. import java.util.Arrays; import java.util.Scanner; class Main { private int solution(Body[] body, int n){ int max = body[0].w; int count = 1; for (int i = 1; i..

https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 이 문제는 DFS로 풀었다. 처음에는 시간 초과가 났는데 메모제이션을 활용한다면 이를 극복할 수 있고 메모리 초과 같은 경우는 내가 다리가 놓아질 수 있는 최대 갯수를 확인 안 하고 무작정 높게 잡아서 생긴 문제이다. 이런 부분만 조심하면 바로 구할 수 있다!! 메모제이션을 활용할 때 조합쳐럼 nCr 에 특정 n, r일 때의 값을 저장해야 하기 때문에 이중배열을 사용해서 메모제이션을 활용했다. 외..

https://www.acmicpc.net/problem/1009 1009번: 분산처리 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 정수 a와 b가 주어진다. (1 ≤ a < 100, 1 ≤ b < 1,000,000) www.acmicpc.net 두가지 방식으로 풀었는데 향상된 for문을 쓰냐 안 쓰냐 차이일 뿐이다 ㅋㅋ 이 문제는 Math.pow의 원리를 파악하고 있어야 하고 Math.pow를 이용하면 기본적으로 double 타입이 되므로 int로 구하고자 하면 캐스팅을 해줘야 한다는 것을 인지해야한다. 또한, 규칙으로 인해 특정 범위까지 가면 다시 처음 부터 시작하게 하는 % 로 나머지 구하는 방법을 사용할 때 유의할 점이 있다. 바로 다시 처음..

https://www.acmicpc.net/problem/1032 1032번: 명령 프롬프트 첫째 줄에 파일 이름의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에는 파일 이름이 주어진다. N은 50보다 작거나 같은 자연수이고 파일 이름의 길이는 모두 같고 길이는 최대 50이다. 파일이름은 www.acmicpc.net 이 문제는 맨 처음 것을 toCharArray로 변형 한 뒤 그 다음 부터 각각의 char와 비교하면서 다르면 '?'로 바뀌게 함으로써 구할 수 있는 쉬운 문제이다. 그리고 기존에는 무조건 solution 값에 return값을 줘서 구했는데 void로 해서 바로 콘솔에 찍게 만들 수도 있다. 이런 점은 나중에도 유용하게 이용하자. import java.util.Scanner; class Ma..

후.. 일단 너무 피곤한 상태로 풀어서 그런지 머리가 안 돌아갔다. 물론 어려운 문제이기도 하다 ㅠㅠ 내 혼자 힘으로 풀어 보고 싶지만 너무 시간 잡아 먹는 것도 좋지 않기 때문에 어느 정도 선에서 풀이를 보고자 한다., 밑의 코드는 내가 한 곳 까지 적어놨다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; class Main { private int combi(int n, int i) { int[][] ch = new int[11][11]; if (ch[n][i] > 0) return ch[n][i]; if(n == i || i == 0) return 1; else return ch[..

https://www.acmicpc.net/problem/1152 1152번: 단어의 개수 첫 줄에 영어 대소문자와 공백으로 이루어진 문자열이 주어진다. 이 문자열의 길이는 1,000,000을 넘지 않는다. 단어는 공백 한 개로 구분되며, 공백이 연속해서 나오는 경우는 없다. 또한 문자열 www.acmicpc.net 이 문제를 풀기 위해서는 세가지 지식이 필요하다. strip : 양쪽 공백 삭제 split : 내가 원하는 형태로 분리 가능 공백으로 적을때 strip 하면 ""가 남는것 이렇게 세 가지이다. 이 세 가지를 잘 이해하고 있다면 너무 쉽게 푼다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.A..

https://www.acmicpc.net/problem/1141 1141번: 접두사 접두사X 집합이란 집합의 어떤 한 단어가, 다른 단어의 접두어가 되지 않는 집합이다. 예를 들어, {hello}, {hello, goodbye, giant, hi}, 비어있는 집합은 모두 접두사X 집합이다. 하지만, {hello, hell}, {giant, www.acmicpc.net 시간복잡도 : O(N^3) 사용한 방법 : Comparable 정렬 -> 우선, 이 문제는 Comparable로 객체를 정렬시킨 뒤에 풀어야 하는 문제이다. 그렇게 해야 문제를 조금 더 쉽게 접근이 가능하다. 그런데, 이상하게 이 문제가 틀렸다... 예시 코드는 다 맞느데 말이다.. import java.io.BufferedReader; ..