백준] 11057 : 오르막 수

BOJ에서 다음 문제들을 쭉 순서대로 풀어본다.  boj.kr/문제번호 <= 형태로 검색하면 된다.

DP - 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052

 

 

1시간 넘어가면 풀던 짓을 그만두고 반드시 AC받은 코드 찾아보기 (설명이 꼭 달려있는 코드를 읽자)

그리고 푼 다음에는 반드시 다른 사람의 코드를 봐야 한다.

특히 자신만의 가상의 스승을 잡고 그 분의 코드를 보는 것도 좋은 방법이라 생각한다.

너무 갓갓들은 이상한 방식으로도 짜는 경우도 있기 때문에 적당한 사람을 선택해야 한다.

 

알고리즘 문제풀이(PS) 시작하기

 

내가 애용하는 IDE 사이트

(IDE 자동 완성이 불가능하기 때문에 사용하는 중)

Ideone.com

---

 

11057번: 오르막 수

문제  : 

오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다.

예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다.

수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다.

 

 

입력  : 

첫째 줄에 N (1 ≤ N ≤ 1,000)이 주어진다.

 

 

출력  : 

첫째 줄에 길이가 N인 오르막 수의 개수를 10,007로 나눈 나머지를 출력한다.

 

 

 

 

접근 방법

1번. 초기화

  1) dp라는 배열은 int dp[1001][10]으로 초기화해줍니다.
  2) 예제 1번을 참고합니다. 1 입력일 때, 출력은 10입니다. 따라서 i가 0부터 9까지라면 dp[i][1] = 1로 초기화할 수 있습니다.


2번. 점화식

  1) 이 문제는 for문 세 개를 겹쳐서 풉니다.
       1번 for문은 N까지 / 2번 for문은 0부터 9까지 / 3번 for문은 2번 for문부터 9까지입니다.
       (왜냐하면 만약 0으로 끝나면 그 다음 자리는 0부터 9가 올 수 있고, 3으로 끝나면 3부터 9가 올 수 있기 때문입니다.)

  따라서 

  마지막 자리가 0이면 dp[N][0~9] += dp[N][0]

  마지막 자리가 1이면 dp[N][0~9] += dp[N][1]

  마지막 자리가 9면 dp[N][0~9] += dp[N-1][9]

 

  최종 점화식은 dp[ 2~N까지 ] [ 0~9까지 ] = dp[ (2~N까지) - 1 ] [ 0~9까지 ]

내가 처음 생각한 접근 방법 (헷갈리는 부분)

// 처음 적어본 코드

#include <iostream>
#define MOD 10007
typedef long long ln;

using namespace std;


int dp[1001][10];
int N;
ln result;

int main() {

	int cnt = 0;
	
	cin >> N;
	
	for(int i = 0; i <= 10; i++){
		dp[1][i] = 1;
		dp[2][i] = cnt;
		
		cnt++;

	}
	
	for(int i = 1; i <= N; i++){
		for(int j = 0; j <= 10; j++){
			if(i <= j){
				//dp[i][j] = dp[i - 1][j + 1];
			}
		}
	}
	
	for(int i = 0; i <= 10; i++){
		result += dp[N][i] % MOD;
	}
	cout << result % MOD << endl;

	return 0;
}

 

 1. int dp[1001][10]; N은 1 <= N <= 1,000이므로.
     dp[1][i]..(i는 0부터 9까지)는 1로 초기화
 
 2. 인접한 수가 같아도 오름차순 / 수는 0부터 시작 가능
 
 3. 점화식( i는 <= N & j는 9까지일 때 )
     3-1. 만약 ***0_이면 0~9까지 가능
     3-2. 만약 ***2_이면 2부터 9까지 가능
     3-3. 만약 ***9_이면 9만 가능

     dp[i][j] = dp[ i + 1][ j + 1 ]
 

    => i <= j여야 오름차순인 수가 가능해짐.

 

 

?? : 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다.

-> 이 부분에서 91111은 오르막 수가 아니라고 했다.

2 입력 시 55 출력..을 보니까 피보나치 수열방식으로 풀어야 할까..? 라는 생각을 했다.

 

하지만 위의 초록색 문장이...

911111은 오르막 수가 아니라면, 처음 시작 수가 다른 수보다 클 때 오르막 수가 아니라는 것을 명시해야 하나?

라는 생각을 해보았당..

------------------------------------------------------------------------------ 40분

다른 해석 참조

위에 내가 접근한 점화식 만드는 방법은 비슷하다.

마지막 자리가 0이면 dp[N][0~9] += dp[N][0]
마지막 자리가 1이면 dp[N][0~9] += dp[N][1]
마지막 자리가 9면 dp[N][0~9] += dp[N-1][9]

따라서 최종 점화식은 dp[ 2~N ][ k ( j~9) ] = dp[ (2~N) - 1 ][ j (0~9) ]

 

 

 

 

정답 코드

#include <iostream>
#define MOD 10007

using namespace std;

int dp[1001][10], N, sum;

int main() {

	cin >> N;
	
	//예제 1에서 참고하여 dp[1][i] 부분 1로 초기화
	for(int i = 0; i < 10; i++){
		dp[1][i] = 1;
	}
	
	
	for(int i = 2; i <= N; i++){
		for(int j = 0; j < 10; j++){
			for(int k = j; k < 10; k++){
			 // 더해주기
			  //dp[i][j] += dp[j - 1][k] % MOD;
				dp[i][j] += dp[i - 1][k];
				dp[i][j] %= MOD;
			}
		}
	}
	
	for(int i = 0; i < 10; i++){
		sum = (sum + dp[N][i]) % MOD;
	}
	
	cout << sum % MOD;
	
	return 0;
}

 

 

 

 

백준 11057번 오르막 수

[백준 BOJ][DP] 11057 오르막 수