Hayden's Archive
[알고리즘] 백준 - 다이나믹 프로그래밍 관련 문제 3 본문
알고리즘 문제 출처 : 백준 - 15988번 : 1, 2, 3 더하기 3 https://www.acmicpc.net/problem/15988
15988번: 1, 2, 3 더하기 3
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.
www.acmicpc.net
내가 작성한 코드
import java.util.Scanner;
public class Main {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
long[] check = new long[1000001];
check[1] = 1;
check[2] = 2;
check[3] = 4;
for(int i=4; i<check.length; i++) {
check[i] = check[i-1] + check[i-2] + check[i-3];
check[i] %= 1000000009;
}
for(int i=0; i<t; i++) {
int n = sc.nextInt();
System.out.println(check[n]);
}
}
}
알고리즘 문제 출처 : 백준 - 1149번 : RGB거리 https://www.acmicpc.net/problem/1149
1149번: RGB거리
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,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[][] price = new int[n+1][3]; //각 집마다의 RGB 비용
int[][] total = new int[n+1][3]; //RGB 최소 비용합
for(int i=1; i<=n; i++) {
price[i][0] = sc.nextInt(); //R 비용
price[i][1] = sc.nextInt(); //G 비용
price[i][2] = sc.nextInt(); //B 비용
}
/* 1번 집까지의 RGB 비용 총합 초기화 */
total[1][0] = price[1][0];
total[1][1] = price[1][1];
total[1][2] = price[1][2];
for(int i=2; i<=n; i++) {
total[i][0] = Math.min(total[i-1][1], total[i-1][2]) + price[i][0];
total[i][1] = Math.min(total[i-1][0], total[i-1][2]) + price[i][1];
total[i][2] = Math.min(total[i-1][1], total[i-1][0]) + price[i][2];
}
int min = Math.min(Math.min(total[n][0], total[n][1]), total[n][2]);
System.out.println(min);
}
}
알고리즘 문제 출처 : 백준 - 1309번 : 동물원 https://www.acmicpc.net/problem/1309
1309번: 동물원
첫째 줄에 우리의 크기 N(1≤N≤100,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[][] check = new int[n+1][3];
check[1][0] = 1;
check[1][1] = 1;
check[1][2] = 1;
int divisor = 9901;
for(int i=2; i<=n; i++) {
check[i][0] = (check[i-1][0] + check[i-1][1] + check[i-1][2]) % divisor;
check[i][1] = (check[i-1][0] + check[i-1][2]) % divisor;
check[i][2] = (check[i-1][0] + check[i-1][1]) % divisor;
}
System.out.println((check[n][0] + check[n][1] + check[n][2]) % divisor);
}
}
알고리즘 문제 출처 : 백준 - 11057번 : 오르막 수 https://www.acmicpc.net/problem/11057
11057번: 오르막 수
오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수�
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[][] check = new int[n+1][10];
for(int i=0; i<10; i++) {
check[1][i] = 1;
}
int divisor = 10007;
for(int i=2; i<=n; i++) {
for(int j=0; j<10; j++) {
for(int l=j; l<10; l++) {
check[i][j] += (check[i-1][l]) % divisor;
}
}
}
int answer = 0;
for(int i=0; i<10; i++) {
answer += check[n][i];
answer %= divisor;
}
System.out.println(answer);
}
}
알고리즘 문제 출처 : 백준 - 9465번 : 스티커 https://www.acmicpc.net/problem/9465
9465번: 스티커
문제 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티
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();
for(int i=0; i<n; i++) {
int m = sc.nextInt();
long[][] sticker = new long[m+1][3]; //위쪽 스티커 1, 아래쪽 스티커 2
/* 스티커별 점수 초기화 */
for(int j=1; j<=m; j++) { //위쪽 스티커
sticker[j][1] = sc.nextInt();
}
for(int j=1; j<=m; j++) { //아래쪽 스티커
sticker[j][2] = sc.nextInt();
}
/* check 배열 선언 및 앞쪽값 일부 할당 */
long[][] check = new long[m+1][3];
for(int j=1; j<=m; j++) {
/* j번째 자리에 스티커를 떼지 않은 경우 */
check[j][0] = Math.max(Math.max(check[j-1][0], check[j-1][1]), check[j-1][2]);
/* j번째 위쪽 자리에서 스티커를 뗀 경우 */
check[j][1] = Math.max(check[j-1][0], check[j-1][2]) + sticker[j][1];
/* j번재 아래쪽 자리에서 스티커를 뗀 경우 */
check[j][2] = Math.max(check[j-1][0], check[j-1][1]) + sticker[j][2];
}
System.out.println(Math.max(Math.max(check[m][0], check[m][1]), check[m][2]));
}
}
}
알고리즘 문제 출처 : 백준 - 2156번 : 포도주 시식 https://www.acmicpc.net/problem/2156
2156번: 포도주 시식
효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규
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[] wine = new int[n+1];
int[][] check = new int[n+1][3];
for(int i=1; i<=n; i++) {
wine[i] = sc.nextInt();
}
/* check[i][0] i번째 포도주를 마시지 않은 경우
* (i-1번째 포도주를 마시지 않았거나, 마셨거나, 2번 연속으로 마셨거나)
* check[i][1] i번째 포도주를 1번 연속으로 마신 경우
* (i-1번째 포도주를 마시지 않음)
* check[i][2] i번째 포도주를 2번 연속으로 마신 경우
* (i-1번째 포도주를 마심)
*/
check[1][0] = 0;
check[1][1] = wine[1];
check[1][2] = wine[1];
for(int i=2; i<=n; i++) {
check[i][0] = Math.max(Math.max(check[i-1][0], check[i-1][1]), check[i-1][2]);
check[i][1] = check[i-1][0] + wine[i];
check[i][2] = check[i-1][1] + wine[i];
}
System.out.println(Math.max(Math.max(check[n][0], check[n][1]), check[n][2]));
}
}
알고리즘 문제 출처 : 1932번 : 정수 삼각형 https://www.acmicpc.net/problem/1932
1932번: 정수 삼각형
문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최�
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[][] tri = new int[n][n]; //입력값을 받는 배열
int[][] sum = new int[n][n]; //n행 n열에서의 최대합
/* 입력값을 받음 */
for(int i=0; i<n; i++) {
for(int j=0; j<=i; j++) {
tri[i][j] = sc.nextInt();
}
}
/* 최대합 배열 0행 0열 초기화 */
sum[0][0] = tri[0][0];
/* 최대합을 구해서 배열에 할당한다.
* 점화식을
* sum[i][j] = Math.max(sum[i-1][j-1], sum[i-1][j]) + tri[i][j] 로
* 세우면 j를 1부터 시작해야 하는데, 그렇게 되면 0열의 값들이 누락되게 됨.
*/
for(int i=1; i<n; i++) {
for(int j=0; j<=i; j++) {
sum[i][j] = sum[i-1][j] + tri[i][j];
if(j > 0 && sum[i][j] < sum[i-1][j-1] + tri[i][j]) {
sum[i][j] = sum[i-1][j-1] + tri[i][j];
}
}
}
/* n-1행의 최댓값을 구함 */
int max = sum[n-1][0];
for(int j=0; j<n; j++) {
if(sum[n-1][j] > max) {
max = sum[n-1][j];
}
}
System.out.println(max);
}
}
알고리즘 문제 출처 : 백준 - 11055번 : 가장 큰 증가 부분 수열 https://www.acmicpc.net/problem/11055
11055번: 가장 큰 증가 부분 수열
수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수�
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[] a = new int[n]; //입력받을 배열
int[] sum = new int[n]; //sum[i] : a[i]가 가장 마지막에 오는 합
/* 입력받은 값을 배열에 할당 */
for(int i=0; i<n; i++) {
a[i] = sc.nextInt();
}
/* 배열 sum에 있는 값들은 모두 기본값인 0이다.
* 그러므로 sum[i]에 a[i]를 먼저 할당해준다.
* j번째 수는 i번째 수보다 앞에 있는 수인데
* a[i]가 a[j]보다 크고, sum[i]가 sum[j]+a[i]보다 작으면
* sum[i] = sum[j] + a[i]를 할당한다.
*
* 점화식은 sum[i] = max(sum[j] + a[i])
* a[i]가 가장 마지막에 오는 합(sum[i])은
* (i번째보다 앞에 있는 j번째의 값 a[j]가 마지막으로 오는 합) 중에서 가장 큰 값에 a[i]를 더한 값과 같다. */
for(int i=0; i<n; i++) {
sum[i] = a[i];
for(int j=0; j<i; j++) {
if(a[i] > a[j] && sum[i] < sum[j] + a[i]) {
sum[i] = sum[j] + a[i];
}
}
}
/* sum[i](a[i]가 가장 마지막에 오는 합) 중에서 가장 큰 값을 고른다. */
int max = sum[0];
for(int i=0; i<n; i++) {
if(max < sum[i]) {
max = sum[i];
}
}
System.out.println(max);
}
}
알고리즘 문제 출처 : 백준 - 11722번 : 가장 긴 감소하는 부분 수열 https://www.acmicpc.net/problem/11722
11722번: 가장 긴 감소하는 부분 수열
수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} �
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[] a = new int[n]; //입력받을 배열
int[] count = new int[n]; //count[i] : a[i]가 가장 마지막에 올 때, 개수
for(int i=0; i<n; i++) {
a[i] = sc.nextInt();
}
for(int i=0; i<n; i++) {
count[i] = 1;
for(int j=0; j<i; j++) {
if(a[i] < a[j] && count[i] < count[j] + 1) {
count[i] = count[j] + 1;
}
}
}
int answer = count[0];
for(int i=1; i<n; i++) {
if(answer < count[i]) {
answer = count[i];
}
}
System.out.println(answer);
}
}
알고리즘 문제 출처 : 백준 - 11054번 : 가장 긴 바이토닉 부분 수열 https://www.acmicpc.net/problem/11054
11054번: 가장 긴 바이토닉 부분 수열
첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,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[] input = new int[n]; //입력받을 배열
int[] ascend = new int[n]; //ascend[i] : i번째 값으로 끝나는 증가하는 수열
int[] descend = new int[n]; //descend[i] : i번째 값으로 시작하는 감소하는 수열
/* 값 입력 */
for(int i=0; i<n; i++) {
input[i] = sc.nextInt();
}
/* i번째 값으로 끝나는 증가하는 수열 */
for(int i=0; i<n; i++) {
ascend[i] = 1;
for(int j=0; j<i; j++) {
if(input[i] > input[j] && ascend[i] < ascend[j] + 1) {
ascend[i] = ascend[j] + 1;
}
}
}
/* i번째 값으로 시작하는 감소하는 수열 */
for(int i=n-1; i>=0; i--) {
descend[i] = 1;
for(int j=i+1; j<n; j++) {
if(input[i] > input[j] && descend[i] < descend[j] + 1) {
descend[i] = descend[j] + 1;
}
}
}
/* 최대개수 구하기 */
int answer = ascend[0] + descend[0] -1; //input[0]이 중복으로 2번 들어갔으므로 1을 빼준다.
for(int i=1; i<n; i++) {
if(answer < ascend[i] + descend[i] - 1) {
answer = ascend[i] + descend[i] - 1;
}
}
System.out.println(answer);
}
}
알고리즘 문제 출처 : 백준 - 13398번 : 연속합 2 https://www.acmicpc.net/problem/13398
13398번: 연속합 2
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
www.acmicpc.net
import java.util.Scanner;
public class Main {
//10 -4 3 1 5 6 -35 12 21 -1
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] input = new int[n]; //입력받을 배열
int[] front = new int[n]; //front[i] : 제거할 k번째 앞에 올, i번째까지의 합
int[] back = new int[n]; //back[i] : 제거할 k번째 뒤에 올, i번부터의 합
/* 값 입력 */
for(int i=0; i<n; i++) {
input[i] = sc.nextInt();
}
/* k번째 앞에 올 수 */
for(int i=0; i<n; i++) {
front[i] = input[i];
if(i>0 && front[i] < front[i-1] + input[i]) {
front[i] = front[i-1] + input[i];
}
}
/* k번째 뒤에 올 수 */
for(int i=n-1; i>=0; i--) {
back[i] = input[i];
if(i < n-1 && back[i] < back[i+1] + input[i]) {
back[i] = back[i+1] + input[i];
}
}
int max = front[0];
/* k번째 수를 빼지 않고 진행할 경우 */
for(int i=0; i<n; i++) {
if(max < front[i]) {
max = front[i];
}
}
/* k번째 수를 뺄 경우 */
for(int i=0; i<n; i++) {
if(i-1>=0 && i+1<n && max < front[i-1] + back[i+1]) {
max = front[i-1] + back[i+1];
}
}
System.out.println(max);
}
}
알고리즘 문제 출처 : 17404번 : RGB거리 2 https://www.acmicpc.net/problem/17404
17404번: RGB거리 2
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,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[][] cost = new int[n+1][3];
int[][] check = new int[n+1][3];
int max = 1000 * 1000 + 1;
/* 입력값을 cost 배열에 할당 */
for(int i=1; i<=n; i++) {
for(int j=0; j<3; j++) {
cost[i][j] = sc.nextInt();
}
}
for(int j=0; j<3; j++) {
/* j가 있는 for문을 돌 때마다 1번집의 색깔이 cost[1][j]로 결정됨 */
for(int i=0; i<3; i++) {
if(i==j) {
check[1][i] = cost[1][j];
}else {
check[1][i] = max;
}
}
/* check[i][0] i번째 집의 색깔이 R일 때의 최소합 */
for(int i=2; i<=n; i++) {
check[i][0] = Math.min(check[i-1][1], check[i-1][2]) + cost[i][0];
check[i][1] = Math.min(check[i-1][0], check[i-1][2]) + cost[i][1];
check[i][2] = Math.min(check[i-1][1], check[i-1][0]) + cost[i][2];
}
/* 위에서 결정된 1번집의 색깔과 n번집의 색깔을 다르게 해서 최소합 비교 */
for(int i=0; i<3; i++) {
if(i==j) continue;
if(max > check[n][i]) {
max = check[n][i];
}
}
}
System.out.println(max);
}
}
