Hayden's Archive
[알고리즘] 백준 - 다이나믹 프로그래밍 관련 문제 1 본문
알고리즘 문제 출처) 백준 1463번 : 1로 만들기 https://www.acmicpc.net/problem/1463
1463번: 1로 만들기
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.
www.acmicpc.net
내가 작성한 코드
Bottom-Up 방식(반복문으로 구현)
import java.util.Scanner;
public class Main {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] record = new int[n+1];
for(int i=2; i<=n; i++) {
record[i] = record[i-1] + 1;
if(i%2==0 & record[i]>record[i/2]+1) {
record[i] = record[i/2]+1;
}
if(i%3==0 & record[i]>record[i/3]+1) {
record[i]=record[i/3]+1;
}
}
System.out.println(record[n]);
}
}
Top-Down 방식(재귀로 구현)
import java.util.Scanner;
public class Main {
static int[] record; //n=i일 때 연산 횟수의 최솟값
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
record = new int[n+1];
System.out.println(dynamic(n));
}
public static int dynamic(int n) {
if(n==1) return 0; //1로 만들어야 하는데 1이 입력되면 0
if(record[n]>0) return record[n]; //값이 할당되었다면 그대로 리턴
/* dynamic(1)일 때부터 값이 있으므로 n = 2,3,4,..., n 순으로 할당 */
record[n] = dynamic(n-1)+1;
if(n%2==0) {
int result = dynamic(n/2)+1;
if(record[n]>result) {
record[n] = result;
}
}
if(n%3==0) {
int result = dynamic(n/3)+1;
if(record[n]>result) {
record[n] = result;
}
}
return record[n];
}
}
알고리즘 문제 출처) 백준 11726번 : 2×n 타일링 https://www.acmicpc.net/problem/11726
11726번: 2×n 타일링
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
www.acmicpc.net
내가 작성한 코드
- 문제를 푸는 원리
- 처음에 n=1일 경우를 고려하지 않고 record[2]를 할당해서 계속 런타임 에러가 났다. 런타임 에러의 원인을 깨닫고 n이 2보다 크거나 같을 경우에 할당하게 했더니 성공했다.
import java.util.Scanner;
public class Main {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] record = new int[n+1];
record[1] = 1;
if(n>=2) record[2] = 2;
for(int i=3; i<=n; i++) {
record[i] = (record[i-1] + record[i-2]) % 10007;
}
System.out.println(record[n]);
}
}
알고리즘 문제 출처) 백준 9095번 1, 2, 3 더하기 https://www.acmicpc.net/problem/9095
9095번: 1, 2, 3 더하기
문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는
www.acmicpc.net
내가 작성한 코드
정수 n을 1,2,3의 합으로 나타내는 방법의 가지수를 D[n]이라고 할 때 D[n]을 마지막에 1을 더해주는 경우, 마지막에 2를 더해주는 경우, 마지막에 3을 더해주는 경우로 나눠서 D[n] = D[n-1] + D[n-1] + D[n-3]으로 나타낼 수 있다. 이 때, n이 2, 3보다 작을 때 배열이 넘치지 않도록 조건을 달아줘야 한다.
import java.util.Scanner;
public class Main {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for(int i=0; i<n; i++) {
int m = sc.nextInt();
int[] record = new int[m+1];
record[1] = 1;
if(m>=2) record[2] = 2;
if(m>=3) record[3] = 4;
for(int j=4; j<=m; j++) {
record[j] = record[j-1] + record[j-2] + record[j-3];
}
System.out.println(record[m]);
}
}
}
알고리즘 문제 출처) 백준 11052번 : 카드 구매하기 https://www.acmicpc.net/problem/11052
11052번: 카드 구매하기
첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)
www.acmicpc.net
내가 작성한 코드
import java.util.Scanner;
public class Main {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] card = new int[n+1]; //카드팩의 가격
int[] price = new int[n+1]; //i개의 카드를 구하기 위해 지불해야 하는 최대 가격
for(int i=1; i<=n; i++) {
int m = sc.nextInt();
card[i] = m;
}
for(int i=1; i<=n; i++) {
for(int j=1; j<=i; j++) {
if(price[i] < price[i-j] + card[j]) {
price[i] = price[i-j] + card[j];
}
}
}
System.out.println(price[n]);
}
}
알고리즘 문제 출처) 16194번 카드 구매하기 2 https://www.acmicpc.net/problem/16194
16194번: 카드 구매하기 2
첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)
www.acmicpc.net
내가 작성한 코드
최솟값을 구할 때는 배열에 기본적으로 0이 들어가는 것을 감안하고 card에 값을 할당할 때 price에도 같이 값을 할당해주면 된다.
import java.util.Scanner;
public class Main {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] card = new int[n+1]; //카드팩의 가격
int[] price = new int[n+1]; //i개의 카드를 구하기 위해 지불해야 하는 최대 가격
for(int i=1; i<=n; i++) {
int m = sc.nextInt();
card[i] = price[i] = m;
}
for(int i=1; i<=n; i++) {
for(int j=1; j<=i; j++) {
if(price[i] > price[i-j] + card[j]) {
price[i] = price[i-j] + card[j];
}
}
}
System.out.println(price[n]);
}
}
알고리즘 문제 출처) 백준 15990번 : 1, 2, 3 더하기 5 https://www.acmicpc.net/problem/15990
15990번: 1, 2, 3 더하기 5
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.
www.acmicpc.net
내가 작성한 코드
다이나믹 프로그래밍은 코드를 짜는 것보다 점화식을 생각해내는 게 어렵다. check[n][a]를 맨 끝에 a(a=1,2,3)를 더했을 때 n이 나오는 방법의 수라고 정의하고, check[1], check[2], check[3]의 요소들의 값을 모두 채워준 후 다이나믹 프로그래밍을 돌린다. 수의 범위가 커지는 것을 고려하여 1000000009로 나눈 나머지를 구하는 것이므로, check는 long형으로 선언되어야 한다.
import java.util.Scanner;
public class Main {
public static void main(String args[]) {
final int limit = 1000000009;
long[][] check = new long[100001][4];
check[1][1] = 1;
check[1][2] = 0;
check[1][3] = 0;
check[2][1] = 0;
check[2][2] = 1;
check[2][3] = 0;
check[3][1] = 1;
check[3][2] = 1;
check[3][3] = 1;
for(int i=4; i<check.length; i++) {
check[i][1] = (check[i-1][2] + check[i-1][3]) % limit;
check[i][2] = (check[i-2][1] + check[i-2][3]) % limit;
check[i][3] = (check[i-3][1] + check[i-3][2]) % limit;
}
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for(int i=1; i<=n; i++) {
int m = sc.nextInt();
System.out.println((check[m][1]+check[m][2]+check[m][3]) % limit);
}
}
}
알고리즘 문제 출처) 백준 10844번 : 쉬운 계단 수
내가 작성한 코드
이 문제는 점화식을 생각해내는 게 어렵다. 여기서 check[n][a]는 길이가 n이면서, a(0<=a<=9)가 마지막 수인 계단 수를 뜻한다. 따라서 check[n][a] = check[n-1][a-1] + check[n-1][a+1]이 된다. 단, 0과 9는 예외이므로 따로 처리해줘야 한다. 0은 자신보다 1 큰 수인 1만 생각해야 하고, 9는 자신보다 1 작은 수인 8만 생각해야 한다.
import java.util.Scanner;
public class Main {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long[][] check = new long[n+1][10];
long limit = 1000000000;
for(int j=1; j<=9; j++) {
check[1][j] = 1;
}
for(int i=2; i<=n; i++) {
for(int j=0; j<=9; j++) {
if(j==0) {
check[i][0] = check[i-1][1] % limit;
}
else if(j==9) {
check[i][9] = check[i-1][8] % limit;
}
else {
check[i][j] = (check[i-1][j-1] + check[i-1][j+1]) % limit;
}
}
}
long total = 0;
for(int j=0; j<10; j++) {
total = (total + check[n][j]) % limit;
}
System.out.println(total);
}
}
알고리즘 문제 출처) 2193번 : 이친수 https://www.acmicpc.net/problem/2193
2193번: 이친수
0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않
www.acmicpc.net
내가 작성한 코드
check[n][a]를 n자리 수일 때 마지막이 a(a=0 또는 a=1)인 경우의 수로 잡고 마지막에 0이 오는 경우와 1이 오는 경우를 다르게 처리해주면 된다.
import java.util.Scanner;
public class Main {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long[][] check = new long[n+1][2];
check[1][1] = 1;
for(int i=2; i<=n; i++) {
check[i][0] = check[i-1][0] + check[i-1][1];
check[i][1] = check[i-1][0];
}
System.out.println(check[n][0]+check[n][1]);
}
}
