알고리즘 기초 2/1 - 400

14862 단어 baekjoonbaekjoon

400 - 다이나믹 프로그래밍1

1로 만들기 - 1463

나의 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] dp = new int[n + 1];
		for (int i = 2; i < dp.length; i++) {
			if (i % 3 == 0) {
				dp[i] = Math.min(dp[i - 1], dp[i / 3]) + 1;
			}
			if (i % 2 == 0) {
				dp[i] = Math.min(dp[i - 1], dp[i / 2]) + 1;
			}
			if (i % 3 != 0 && i % 2 != 0) {
				dp[i] = dp[i - 1] + 1;
			}
			if (i % 6 == 0) {
				dp[i] = Math.min(dp[i / 3], dp[i / 2]) + 1;
			}
		}
		System.out.println(dp[n]);
	}
}

다른 분들 풀이를 보니 1을 먼저 빼고 난 뒤 나눈 값과 계산하는 풀이가 일반적인 풀이 같은데, 문제의 흐름을 따라가다 보니(3먼저 나누고 2나누고 1을 빼고) 불필요한 추가 연산(최소공배수)이 포함 된 것 같다.

2×n 타일링 - 11726

나의 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] dp = new int[n + 1];
		dp[1] = 1;
		if (n >= 2) {
			dp[2] = 2;
		}
		for (int i = 3; i < dp.length; i++) {
			dp[i] = dp[i - 1] + dp[i - 2];
			dp[i] = dp[i] % 10007;
		}
		System.out.println(dp[n]);
	}
}

타일을 옆으로 한줄씩 이어 붙인 것으로 점화식은 다음과 같다
dp[n] = dp[n-1] + dp[n-2]
그리고 10007로 나누라는 것은 수가 무수히 커지거나 하면 정수범위를 초과하기에 나머지 값에서(작은 수)에서 계산 되도록 하라는 의미

2×n 타일링 2 - 11727

나의 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] dp = new int[n + 1];
		dp[1] = 1;
		if (n >= 2) {
			dp[2] = 3;
		}
		for (int i = 3; i < dp.length; i++) {
			dp[i] = dp[i - 1] + dp[i - 2] * 2;
			dp[i] = dp[i] % 10007;
		}
		System.out.println(dp[n]);
	}
}

2×n 타일링과 비슷한 문제이다.
다만 2×2의 타일이 추가 되었는데 이는 2×2의 크기는 2×1타일을 2개씩 표현할 수 있다. 따라서 점화식은 다음과 같다
dp[n] = dp[n-1] + dp[n-2] × 2

1, 2, 3 더하기 - 9095

나의 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] dp = new int[12];
		dp[1] = 1;
		dp[2] = 2;
		dp[3] = 4;
		for (int i = 0; i < n; i++) {
			int m = Integer.parseInt(br.readLine());
			for (int j = 4; j < dp.length; j++) {
				dp[j] = dp[j - 1] + dp[j - 2] + dp[j - 3];
			}
			System.out.println(dp[m]);
		}
	}
}

점화식은 다음과 같다
dp[n] = dp[n-1] + dp[n-2] + dp[n-3]

ps. 규칙으로 찾아서 해결했는데 사실 밑에 있는 문제(15990)를 해결 하기 위해서는 정확한 풀이를 알아야 한다.(정확한 풀이는 15990 문제 참조)

카드 구매하기 - 11052

나의 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] input = new int[n + 1];
		int[] dp = new int[n + 1];
		String[] value = br.readLine().split(" ");
		for (int i = 1; i < input.length; i++) {
			input[i] = Integer.parseInt(value[i - 1]);
		}
		for (int i = 1; i < dp.length; i++) {
			for (int j = 1; j <= i; j++) {
				dp[i] = Math.max(dp[i], dp[i - j] + input[j]);
			}
		}
		System.out.println(dp[n]);
	}
}

위 경우에서 N의 크기를 가지는 카드팩과 비교하여 큰 값을 가지는 점화식은 다음과 같다
dp[n] = max(dp[n], dp[n-i] + input[i])
( input[] 은 입력받은 카드팩 값 )

카드 구매하기2 - 16194

나의 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] input = new int[n + 1];
		int[] dp = new int[n + 1];
		String[] value = br.readLine().split(" ");
		for (int i = 1; i < input.length; i++) {
			input[i] = Integer.parseInt(value[i - 1]);
		}
		for (int i = 1; i < dp.length; i++) {
			dp[i] = Integer.MAX_VALUE;
			for (int j = 1; j <= i; j++) {
				dp[i] = Math.min(dp[i], dp[i - j] + input[j]);
			}
		}
		System.out.println(dp[n]);
	}
}

위와 같은 문제지만 다른점은 최솟값을 구하는 것
math.min으로 하면 최초 dp[i] = 0이므로 dp[i]를 Integer.MaxValue()로 초기화 시켜주었다.

1, 2, 3 더하기 5 - 15990

나의 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		long[][] dp = new long[100001][4];
        int mod = 1000000009;
		dp[1][1] = 1;
//		dp[1][2] = 0;
//		dp[1][3] = 0;
//		dp[2][1] = 0;
		dp[2][2] = 1;
//		dp[2][3] = 0;
		dp[3][1] = 1;
		dp[3][2] = 1;
		dp[3][3] = 1;
		for (int i = 0; i < n; i++) {
			int m = Integer.parseInt(br.readLine());
			for (int j = 4; j <= m; j++) {
				dp[j][1] = (dp[j - 1][2] + dp[j - 1][3]) % mod;
				dp[j][2] = (dp[j - 2][1] + dp[j - 2][3]) % mod;
				dp[j][3] = (dp[j - 3][1] + dp[j - 3][2]) % mod;
			}
			System.out.println((dp[m][1] + dp[m][2] + dp[m][3]) % mod);
		}
	}
}

위 설명을 점화식으로 나타내면 다음과 같다
dp[수][경우의 수들 중 끝의 수]
dp[n][1] = dp[n-1][2] + dp[n-1][3]
dp[n][2] = dp[n-2][1] + dp[n-2][3]
dp[n][3] = dp[n-3][1] + dp[n-3][2]

ex) 4의 경우의 수들 중 끝이 1인 경우 : (1 + 2 + 1), (3 + 1)임
이는 곧 3의 경우의 수들 중 끝이 2 또는 3인 경우 : (1 + 2), (3)
위 경우에서 뒤에 1을 더한 것 과 같음 -> (1 + 2) + 1), (3) + 1)

이친수 - 2193

나의 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class 이친수 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		long[][] dp = new long[n + 1][2];
		dp[1][1] = 1;// 맨 앞은 무조건 1 이여야 하므로
		if (n >= 2) {
			dp[2][0] = 1;// 그 다음 자리는 무조건 0 이어야 하므로
		}
		for (int i = 3; i < dp.length; i++) {
			for (int j = 0; j < dp[0].length; j++) {
				dp[i][0] = dp[i - 1][1] + dp[i - 1][0];
				dp[i][1] = dp[i - 1][0];
			}
		}
		long answer = dp[n][0] + dp[n][1];
		System.out.println(answer);
	}
}

이차원 배열로 [자릿수][해당 자릿수에 가장 마지막에 위치한 수]
자릿수에 가장 마지막에 위치 할 수는 0 과 1 뿐이므로 전 자릿수에서 올 수 있는 수들을 더해준다. 따라서 점화식은 다음과 같다

  • 끝이 0 일 경우
    dp[n][0] = dp[n-1][1] + dp[n-1][0]

  • 끝이 1일 경우
    dp[n][1] = dp[n-1][0]

    하지만 위 사진을 보면 알겠지만 결국에는
    dp[n] = dp[n-1] + dp[n-2]를 충족한다.

쉬운 계단 수 - 10844

나의 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[][] dp = new int[n + 1][10];
		int mod = 1000000000;
		for (int i = 1; i < dp[0].length; i++) {
			dp[1][i] = 1;
		}
		for (int i = 2; i < dp.length; i++) {
			for (int j = 0; j < dp[0].length; j++) {
				if (j == 0) {
					dp[i][j] = dp[i - 1][1];
				}else if (j == 9) {
					dp[i][j] = dp[i - 1][8];
				}else {
					dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];
				}
				dp[i][j] %= mod;
			}
		}
		long answer = 0;
		for (int i = 0; i < dp[0].length; i++) {
			answer += dp[n][i];
		}
		System.out.println(answer % mod);
	}

}

이친수 문제와 같은 유형이다.
다만 이 문제는 가장 끝 자리가 0일 경우와 9일 경우의 두가지 상황을 고려해야 한다.
끝자리가 0일 경우 => 그 다음에 올 수 있는 수는 1뿐
끝자리가 9일 경우 => 그 다음에 올 수 있는 수는 8뿐
그 외에는 => +1 그리고 -1한 수가 올 수 있음
따라서 점화식은 다음과 같다.

끝자리가 0 => dp[n][0] = dp[n-1][1]
끝자리가 9 => dp[n][9] = dp[n-1][8]
그 외(1 ~ 8) => dp[n][i] = dp[n-1][i-1] + dp[n-1][i+1]

가장 긴 증가하는 부분수열 - 11053

나의 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] input = new int[n + 1];
		int[] dp = new int[n + 1];
		String[] temp = br.readLine().split(" ");
		for (int i = 1; i < input.length; i++) {
			input[i] = Integer.parseInt(temp[i - 1]);
			dp[i] = 1;
		}
        int answer = dp[1];
		for (int i = 2; i < dp.length; i++) {
			for (int j = 1; j < i; j++) {
				if (input[i] > input[j]) {
					dp[i] = Math.max(dp[i], dp[j] + 1);
				}
			}
			answer = Math.max(answer, dp[i]);
		}
		System.out.println(answer);
	}
}

먼저 사진의 case1의 경우 일반적으로 풀었을 것으로 생각된다. 점화식은
input[i] > input[j] => max(dp[i], dp[j] + 1)
단 고려할점이 2가지 정도 있다.(내가 틀린 부분)

  1. case2 처럼 dp배열의 초기값을 1로 설정 해주는 부분
  2. case3 처럼 dp배열에서 가장 큰 값을 답으로 출력하는 부분

가장 긴 증가하는 부분수열4 - 14002

나의 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;

public class 가장긴증가하는부분수열4 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int n = Integer.parseInt(br.readLine());
		int[] input = new int[n + 1];
		int[] dp = new int[n + 1];
		String[] temp = br.readLine().split(" ");
		for (int i = 1; i < dp.length; i++) {
			input[i] = Integer.parseInt(temp[i - 1]);
			dp[i] = 1;
		}
        int answer = dp[1];
		for (int i = 2; i < dp.length; i++) {
			for (int j = 1; j < i; j++) {
				if (input[i] > input[j]) {
					dp[i] = Math.max(dp[i], dp[j] + 1);
				}
			}
            answer = Math.max(answer, dp[i]);
		}
		sb.append(answer + "\n");

		Stack<Integer> stack = new Stack<Integer>();
		for (int i = n; i >= 1; i--) {
			if (answer == dp[i]) {
				stack.push(input[i]);
				answer--;
			}
		}
		while (!stack.empty()) {
			sb.append(stack.pop() + " ");
		}
		System.out.println(sb.toString());
	}
}

전 문제에서 추가하여 증가하는 수열까지 출력해줘야 한다.
이때 필요한 것은 구해진 dp배열의 값을 역추적해서 input의 값을 스택에 넣어 출력하는 것이다.

연속합 - 1912

나의 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] input = new int[n + 1];
		int[] dp = new int[n + 1];
		String[] temp = br.readLine().split(" ");
		for (int i = 1; i < dp.length; i++) {
			input[i] = Integer.parseInt(temp[i - 1]);
		}
		int answer = Integer.MIN_VALUE;
		for (int i = 1; i < dp.length; i++) {
			dp[i] = Math.max(dp[i - 1] + input[i], input[i]);
			answer = Math.max(answer, dp[i]);
		}
		System.out.println(answer);
	}
}

점화식은 다음과 같다
dp[n] = max(dp[n-1] + input[n], input[n])
단 가장 큰 값을 구하기 위해 변수 생성시 음수값을 고려하여 Integer.MIN_VALUE로 초기화함

제곱수의 합 - 1699

나의 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] dp = new int[n + 1];
		for (int i = 1; i < dp.length; i++) {
			dp[i] = i;
			int j = 1;
			while (Math.pow(j, 2) <= i) {
				dp[i] = Math.min(dp[i], dp[i - (int) Math.pow(j, 2)] + 1);
				j++;
			}
		}
		System.out.println(dp[n]);
	}
}

점화식은 다음과 같다
dp[n] = min(dp[i], dp[i - j * j] + 1)
다만 무조건 큰 제곱수로 나눈 다고 최솟값이 아니라는 점을 기억해야 한다

합분해 - 2225

나의 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] input = br.readLine().split(" ");
		int n = Integer.parseInt(input[0]);
		int m = Integer.parseInt(input[1]);
		int[][] dp = new int[n + 1][m + 1];
		int mod = 1000000000;
		for (int i = 1; i < dp[0].length; i++) {
			dp[1][i] = i;
		}
		for (int i = 2; i < dp.length; i++) {
			dp[i][1] = 1;
			for (int j = 2; j < dp[0].length; j++) {
				dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % mod;
			}
		}
		System.out.println(dp[n][m]);
	}
}

위의 논리에서 bottom-up 하다보면 중복되는 합이 나타난다.
이를 치환하다보면 점화식은 다음과 같다.
dp[n][m] = dp[n-1][m] + dp[n][m-1]

평균적으로 한문제 푸는데 2시간 가량 소요되었던 것 같다.
문제를 해결하기 위한 논리를 찾는데 어려웠다. 더 많이 생각하고 풀어봐야 할 것 같다.
갈길이 아직 너무 멀다.

JavaScript 배포 이벤트
컴파일링 원리 탑승 작업 2 - LL (1) 문법 분석

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage