1,2,3 더하기 3
정수 n을 1,2,3의 합으로 나타내는 방법의 수를 구하는 문제 (n<=1,000,000)
- int에 들어갈 수 있는 수가 약 21억.
- d[]를 선언할 때 int말고 long으로 선언해주어야 함.
코드
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc= new Scanner(System.in);
long d[] = new long[1000001];
//여기서 int대신 배열 d를 long으로 사용해야함!
d[0]=1; //초기화
for(int i=1;i<=1000000;i++) {
for(int j=1; j<=3; j++) { //1,2,3
if(i-j >= 0) {
d[i] += d[i-j];
}
}
d[i] %= 1000000009L;
}
int t = sc.nextInt();
while(t-->0) {
int n= sc.nextInt();
System.out.println(d[n]);
}
}
}RGB 거리
RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠함.
또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙.
집 i의 이웃은 집 i-1과 집 i+1이고, 첫 집과 마지막 집은 이웃이 아니다.
처음 집과 마지막 집은 이웃이 아니다.
각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때 모든 집을 칠하는 비용의 최솟값을 구하는 문제.
-
A[i][j] : i번 집을 j번 색으로 칠하는 비용
-
집 i는 i-1과 색이 다르게 칠하면 됨. (단순히 앞집과 색이 다르기만 하면 됨)
-
이웃 집이 연속으로 나옴 -> 연속.
-
연속하는 집을 같은 색으로 색칠할 수 없다.
D[i][j] = i번 집을 색 j로 칠했을 때, 1~i번 집을 칠하는 비용의 최소값.
j = 0 -> 빨강
j = 1 -> 초록
j = 2 -> 파랑
D[i][0] = min(D[i-1][1],D[i-1][2]) + A[i][0]
D[i][1] = min(D[i-1][0],D[i-1][2]) + A[i][1]
D[i][2] = min(D[i-1][0],D[i-1][1]) + A[i][2]
마지막 집을 어떤색으로 색칠하는지를 기록해두는 것.
정답: min(D[N][0], D[N][1], D[N][2])
코드
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc= new Scanner(System.in);
int n= sc.nextInt();
int a[][]= new int [n+1][3];
int d[][]= new int [n+1][3];
for(int i=1;i<=n;i++) {
for(int j=0;j<3;j++) {
a[i][j]=sc.nextInt();
}
}
for(int i=1;i<=n;i++) {
d[i][0] = Math.min(d[i-1][1], d[i-1][2]) + a[i][0];
d[i][1] = Math.min(d[i-1][0], d[i-1][2]) + a[i][1];
d[i][2] = Math.min(d[i-1][0], d[i-1][1]) + a[i][2];
}
System.out.println(Math.min(Math.min(d[n][0], d[n][1]),d[n][2]));
//d[n][0], d[n][1], d[n][2]중에 가장 작은 최소값을 구하는 문제.
}
}=> 문제를 풀기 전에 접근 방법을 생각해보아야 할 것 같다. 접근한 방법을 보면 되게 간단하고 이해도 쉬운데 스스로 접근하는게 어려운듯 하다...
동물원
가로로 두 칸, 세로로 N칸인 동물원이 있다.
가로, 세로로 붙어 있게 배치하면 안됨.
가능한 배치의 수는?
(1칸 최대 1마리)
D[N]= 세로로 N칸인 동물원이 배치의 수.
- 인접에 대한 처리를 해주어야 함.
D[N][M] = 세로로 N칸인 동물원 배치의 수, 마지막 칸 M번 방법을 사용. - D[N][0] = N번 줄에 배치하지 않음.
- D[N][1] = N번 줄의 왼쪽에만 배치함.
- D[N][2] = N번 줄의 오른쪽에만 배치함.
따라서,
- D[N][0] = D[N-1][0] + D[N-1][1] + D[N-1][2]
-> N번줄에 배치하지 않았으니까 N-1에 배치하지않거나, 왼쪽이거나 오른쪽이거나 다 가능. - D[N][1] = D[N-1][0] + D[N-1][2]
-> N번줄의 왼쪽에 배치되었으니까 N-1번째 배치하지않거나, N-1의 오른쪽에 배치 가능. (N-1의 왼쪽은 불가능. 왜냐면 세로로 인접하기 때문) - D[N][2] = D[N-1][0] + D[N-1][1]
-> N번쭐의 오른쪽에 배치가 되었으니까 N-1번째 배치하지 않거나, N-1 왼쪽에 배치 가능. (마찬가지로 N-1 오른쪽은 불가능, 세로로 인접)
코드
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc= new Scanner(System.in);
int n= sc.nextInt();
int d[][] = new int[n+1][3];
d[0][0]=1;
for(int i=1;i<=n;i++) {
d[i][0] = d[i-1][0] + d[i-1][1] + d[i-1][2];
d[i][1] = d[i-1][0] + d[i-1][2];
d[i][2] = d[i-1][0] + d[i-1][1];
for(int j=0;j<3;j++) {
d[i][j] %= 9901;
}
}
System.out.println( (d[n][0] + d[n][1] + d[n][2])%9901);
}
}오르막 수
오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다.
인접한 수가 같아도 오름차순으로 친다.
수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 문제
수는 0으로 시작할 수 있다.
예: 1233345,357,8888,15599
- 쉬운 계단 수 문제랑 비슷함. => 인접한 자리의 차이 1
- 오르막 수 => 인접한 자리가 오름차순.
-
D[i][j] = 수의 길이는 i, 마지막(i번째) 수는 j인 오르막 수의 개수
-
i-1번째에는 올 수 있는 수가 많으니까 변수를 사용. k
-
오르막 수는 수의 자리가 오름차순이기 때문에 k<=j.
-
D[i][j] += D[i-1][k] (0<=k<=j)
-
초기화
- D[1][i]=1. (길이가 1이기 때문)
- D[1][0] = D[0][0]
- D[1][1] = D[0][0] + D[0][1]
- D[1][2] = D[0][0] + D[0][1] + D[0][2]
=> 이렇게 계산해도 전부 1이 나오기 때문에 그냥 D[1][i]는 1로 초기화 해줌.
코드
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc= new Scanner(System.in);
int n= sc.nextInt();
int d[][] = new int[n+1][10];
//초기화해줌.
for(int i=0;i<=9;i++) {
d[1][i] = 1;
}
for(int i=2;i<=n;i++) { //i가 1일 때 초기화했으니까 2부터 시작.
for(int j=0;j<=9;j++) { //j에 올 수 있는 숫자 10가지
for(int k=0;k<=j;k++) { //k는 j보다 작거나 같아야 함.
d[i][j] += d[i-1][k];
d[i][j] %= 10007;
}
}
}
long res=0;
for(int i=0;i<10;i++) {
res += d[n][i];
}
res %= 10007;
System.out.println(res);
}
}최백준 선생님의 코딩테스트 기초 강의를 보고 작성한 글입니다.
