다이나믹프로그래밍4 [백준 2193] 이친수 DP문제입니다. 일단 이걸 직접 손으로 좀 써내려가다보면 피보나치 수열이 나오긴 합니다만... 그냥 문제에 적힌 그대로 풀었습니다. 결과적으로는 비슷하다고 해야하나 같다해야하나 그렇습니다. 일단 1자리 수는 1밖에 없음. 2자리 수는 1 - 0 밖에 없음 3자리 수는 1 - 0 - 0 1 - 0 - 1 존재. 4자리 수는 3자리수 맨뒤 0 -> 0, 1 2가지 가능 3자리수 맨뒤 1 -> 0 1가지 가능. 총 3가지 가능 그림으로 보면서 정리하면 현재 자리수( D[0][N] + D[1][N] ) 의 이천수의 갯수를 구하기 위해선 D[0][N] = D[0][N-1] + D[1][N-1] D[1][N] = D[0][N-1] 두 개의 값을 구해 더하면 됩니다. public class Q2193 { public.. 2019. 4. 5. [백준 1463] 1로 만들기 DP문제입니다. 연산을 수행하는 경우가 3가지가 있죠 1. X%3 == 0 2. X%2 == 0 3. X-=1 배열을 사용해 X까지의 최소 연산 횟수를 구할겁니다. 만약 X가 1일 경우 연산 횟수 -> 0 arr[1] = 0; 2일 경우 -> 2가지 경우가 가능하죠. 나누든지 빼든지. 나눌경우 다음값을 1이 되면서 arr[2] = arr[1] + 1, 결과 : 1 1을 뺄경우 다음값이 1이 되면서 arr[2] = arr[1] + 1, 결과 : 1 동일하네요 3일경우 -> 역시 2가지 경우. 나눌경우 다음값을 1이 되면서 arr[3] = arr[1] + 1, 결과 : 1 1을 뺄경우 다음값이 2가 되면서 arr[3] = arr[2] + 1, 결과 : 2 두가지의 결과값이 다릅니다. 4일경우 -> 2가지 나.. 2019. 4. 5. [백준 1149] RGB거리 DP문제입니다 2차원 배열을 사용했습니다. 맨 마지막줄(N)까지의 최소값을 구하기 위해 이 값을 D[N]이라 하고, 현재 N번째 줄의 값을 P[N] 이라 한다면 D[N] = D[N-1] + P[N]이 되겠죠. 최소값을 구할때는 현재 해당하는 집의 RGB 구할때는 앞집의 색깔 중 현재 집의 색깔을 제외한 나머지 부분을 확인해주시면 됩니다 이 식을 적용해 풀면 됩니다. public class Q1149 { static int[][] arr; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st.. 2019. 4. 5. [백준 1932] 정수 삼각형 DP 문제입니다 일단 삼각형을 입력 받을시 (배열로) 해당 행의 최대값을 바로 구해넣어 주시면 됩니다. 3가지 경우를 체크해주시면 되는데, 2 가지 경우는 왼쪽 대각선으로만 움직엿을 경우와 오른쪽 대각선으로만 움직였을 경우 처리를 해주시고 나머지 한 경우는 (현재 입력값 + 현재의 상단 좌/우값 중) 의 최대값을 넣어주시면 됩니다. 결과적으로 입력받음과 동시에 7 10 15 18 16 15 20 25 20 19 24 30 27 26 24 이런 형태가 되겠죠? 이런 방법으로 푸시면 되겠습니다. public class Q1932 { static int[][] arr; public static void main(String[] args) { Scanner in = new Scanner(System.in); i.. 2019. 4. 4. 이전 1 다음
