아이디어 dp[i] 를 i 번째 숫자를 포함해 연속된 수의 곱이 최대가 될 때의 값이라고 정의하면 dp[i] = Math.max(1, dp[i - 1]) * i번째 숫자 가 된다. i - 1 번째 숫자를 포함해 연속된 수 곱의 최대값이 1보다 작은 경우 i 번째 숫자에 곱했을 때 i 번째 숫자보다 더 작은 값을 얻게 되기 때문이다. 그리고 소수점 이하 셋째 자리까지 출력하는 것은 printf 함수를 사용하면 된다. ＊Math.round( number * 1000) / 1000.0 도 소수점 아래 넷째 자리에서 반올림한 값을 얻을 수 있긴하지만 소수점 아래가 0인 경우 절삭이 되므로 .000 과 같이 무조건 소수점 아래 셋째 자리까지 출력하기 위해서는 적합하지 않은 방법이다. 풀이코드 import java..

아이디어 적록 색약인 케이스와 적록 색약이 아닌 케이스에 대해 각각 깊이 우선 탐색을 진행하고, 깊이 우선 탐색이 총 몇 번 진행됐는지를 확인하면 이것이 곧 구역의 갯수가 된다. 적록 색약인 경우 인접한 색상이 동일한 경우 뿐만 아니라 (R / G) 인 경우도 같은 구역이라고 인식하기 때문에 이 점을 유의해서 dfs 함수를 구현하면 된다. 풀이코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int N; static char[][] board; static int[] dx = {-1, 1, 0, 0}; static int[] dy = {..

아이디어 어떤 건물을 짓기 위해서는 선행되어야 하는 건물들을 다 짓고 난 후에나 이를 지을 수 있다. 그래서 건물 W 를 건설 완료하는데 드는 최소 시간을 dp[W] 로 정의한다면 dp[W] = max(dp[선행 건물1], dp[선행 건물2], ...) + Dw 이 때 선행 건물의 번호가 W 보다 작다는 보장이 없으므로 재귀함수를 통해서 구현하되 한 번 구한 값은 dp 배열에서 가져오는 방식을 사용하면 된다 * 문제에서 Dw 의 범위가 0 부터 시작이기 때문에 건설 완료 시간이 0 인 케이스도 존재가 가능하다. 따라서 dp 배열에 대한 초기화는 -1로 해준다 풀이코드 import java.io.BufferedReader; import java.io.IOException; import java.io.Inp..

아이디어 'taken' 이라는 답안을 'fishcake' 라는 정답으로 바꾸는 과정은 'take' 를 'fishcake' 로 만드는 과정에 마지막 'n' 을 삭제하는 작업이 1번 더해진 것이라고 볼 수 있다. 'piza' 라는 답안을 'pizzaa' 라는 정답으로 바꾸는 과정은 'piza' 를 'pizza' 로 만드는 과정에 마지막 'a' 를 추가하는 작업이 1번 더해진 것이라고 볼 수 있다. 'johnber' 라는 답안을 'johnson' 이라는 정답으로 바꾸는 과정은 'johnbe' 를 'johnso' 으로 만드는 과정에 마지막 'r'을 'n' 으로 바꾸는 작업이 1번 더해진 것이라고 볼 수 있다. 이를 통해 dp[i][j] 를 답안의 i 번째 문자까지, 정답의 j 번째 문자까지 고려했을 때의 수정횟..

아이디어 처음에는 단순히 dfs 를 이용해서 문제를 해결하려 했으나 이 경우 시간초과가 발생하게 된다. 따라서 한 번 방문한 곳에 대한 정보를 저장하는 방식을 사용할 필요가 있어 dfs + dp 방식의 풀이를 적용했다. dp[i][j] 를 (i, j) 에서 (M - 1, N - 1) 까지 갈 수 있는 경로의 수라고 정의한다면 (i, j) 의 상/하/좌/우 좌표 중 좌표값이 (i, j) 의 값보다 더 작은 dp[x][y] 들의 합이 된다. 추가로 dp 배열은 -1 로 초기화를 해주어야 하는데 그 이유는 (i, j) 에서 (M - 1, N - 1) 까지 갈 수 있는 경로의 수가 0 개인 경우도 존재하기 때문이다. 초기값이 아닌 경우 탐색한 것으로 간주하는 방식을 취할 것인데 초기값이 0이면 경로의 수가 0인..

아이디어 dp[i][j] 를 j 번째 숫자가 i번째 구간의 마지막 숫자일 때의 최대값이라고 정의. 이 때 선택할 수 있는 경우의 수는 1) j - 1 번째 숫자가 i 번째 구간의 마지막 숫자인 케이스에 j 번째 숫자를 이어 붙이기 2) i 번째 구간은 j 번째 숫자로만 구성 가 있다. 2) 의 경우 i - 1 번째 구간의 끝 숫자가 j - 2 인 것부터 차례 차례 역으로 탐색해가며 제일 큰 놈을 택하면 된다. 점화식으로 이를 만들어 본다면 dp[i][j] = max(dp[i][j - 1], dp[i - 1][j - 2], dp[i - 1][j - 3], ... ) + numbers[j] i 번째 구간에 대한 탐색을 진행할 때 최소한 2 * i - 1 번째 숫자부터 i 번째 구간이 될 수 있다. 따라서 d..

아이디어 에서 시작해서 가 되는 해가 언제인지를 단순한 브루트포스 방식으로 탐색하려 했으나 시간초과가 발생했다. 따라서 다른 방법이 필요했고 'x - y' 값을 활용하는 방식을 선택했다. 카잉 달력은 처음에는 과 같이 두 값의 차가 0 인 상태에서 시작하지만 둘 중 한 쪽이 한계치에 도달해서 다음 값이 1이 되는 순간 두 값의 차가 바뀌게 된다. 이 점을 활용해서 두 값의 차가 'x - y' 와 같아지는 순간을 찾고 그 지점에서 까지 얼마나 더 지나야 하는지를 알아내면 된다. 예를 들어 의 경우 : 1번째 : 11번째 : 13번째 : 21번째 : 25번째 : 31번째 에서 차가 'x - y' 와 같이지게 되고 31번째가 인데 목표는 이니 31 + (3 - 1) 해서 33번째가 정답이 된다. 이 카잉 달력..

아이디어 어떤 무게를 측정할 수 있는 상태에서 X g 짜리 구슬을 하나 추가한다면 '측정할 수 있는 무게 + X, |측정할 수 있는 무게 - X|' 이 2가지 무게 또한 측정할 수 있게 된다. dp[i][j] 를 i번째 구슬까지 추가했을 때 j 무게를 측정할 수 있는지 여부라고 정의한다면 dp[i][j] = dp[i - 1][j] 또는 dp[i - 1][ | j - j번째 구슬 무게 | ] 또는 dp[i - 1][j + j번째 구슬 무게] 가 된다. 측정할 수 있는 무게의 최대치는 모든 구슬 무게의 합이므로 이 값을 j 의 최대 범위로 설정해서 dp 배열을 만들면 된다. 풀이코드 import java.io.BufferedReader; import java.io.IOException; import java..