[코테]18-오르막 수까지

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);
	}
}

최백준 선생님의 코딩테스트 기초 강의를 보고 작성한 글입니다.