[ 알고리즘 / Kotlin ] 백준 2688 줄어들지 않아

안녕하세요 gyub(귭)입니다 ㅎㅎㅎ

https://www.acmicpc.net/problem/2688

2688번: 줄어들지 않아

dp를 이용해서 푸는 문제인데요!

다소 쉬운편에 속하는 문제 같아요

왜냐면 제가 진짜 dp를 못 풀어서 요즘 한창 dp만 풀고 있는데 이 문제는 비교적 수월하게 풀렸기 때문이죱 ㅎㅎ

갠적인 생각입니다

 

먼저 이 문제를 간단하게 요약하면

 

각 테스트 케이스마다 자릿수가 주어지고 그 자릿수에 해당하는 '줄어들지 않는 수'의 개수를 구하는 문제에요

'줄어들지 않는 수' 란 ?

모든 수의 각 자리 수보다 그 왼쪽 자리 수가 작거나 같을 때 성립하는 수입니다.

예를 들면

123 은 true

111 은 true

100 은 false

112 는 true 이런 식이져

 

처음 접근할 때는 각 자리의 수의 크기를 하나하나 비교해볼까 라는 바보같은 생각을 했어요 ㅠ

제출도 안 해봤지만 시간 초과가 너무나도 뻔한 코드였죠

 

그래서 dp를 이용해서 풀어볼까라고 생각을 했어요

공책에 1자리,2자리까지만 나열해봤더니 규칙이 보였습니다!!!!

 

※ 규칙

n = 1

0

1

2

3

4

5

6

7

8

9

result =10

 

n = 2

0|0

0|1

0|2

...

0|9

===> 10개

1|1

1|2

...

1|9

====>9개

.....

9|9

====>1개

 

result = 10+9+8+7+6+5+4+3+2+1 = 55

 

규칙이 보이시나요??

두 자리 수 부터 앞에 오는 숫자를 기준으로 잡고 기준이 되는 수부터 n-1의 값을 더해주면 됩니다

 

점화식은 

dp[i][j] = dp[i - 1][j] + dp[i][j + 1] 요렇게 되겠네요

이해가 안 가신다면 숫자를 직접 대입하고 나열해보시면 확 와닿을 꺼에요

제가 글솜씨가 매우 정말 너무나도 안 좋기 때문에 ㅎ,,,

 

 

 

 

※ 코드

여기서 저는 dp를 2차원 배열로 해줬어요 자릿수와 '줄어들지 않는 수'의 개수를 나타내기 위함이죠

//dp[n][i]
    dp = Array(65) { LongArray(10) { 0 } }

1자리 일 때는 무조건 10개죠 왜냐 모든 수가 한자리니까!

그래서 일단 

dp[1] = LongArray(10) { 1 }

요렇게 n이 1일때는 1로 초기화를 시켜줬어요 

 

그리고 앞에서 말씀드린 점화식 계산 코드에요

for (i in 2..t) {
        dp[i][9] = 1
        for (j in 8 downTo 0) {
            dp[i][j] = dp[i - 1][j] + dp[i][j + 1]
        }
    }
    answer = dp[t].sum()

맨 앞자리가 9면 줄어들지않는 수는 무조건 9,99,999,9999,99999 이런식으로 하나밖에 없을테니

계산 전에 한 개로 초기화를 시켜주고 8부터 0까지 점화식을 적용시켜줍니다!

여기서 왜 0 부터가 아닌 8부터 돌리냐 하면!

 

나열해보신분들은 아시겠지만

줄어들지 않는 수 의 규칙에 의해 기준이 되는 맨 앞자리의 수보다 커야합니다

그래서 맨 앞자리의 숫자가 커질수록 줄어들지 않는 수의 개수는 작아지기 때문이죠

 

제대로 설명이 됐을지 모르겠지만,,, ( 어렵네요 남에게 설명하는건ㅠㅠ )

 

전체코드는 깃허브에 올려놨습니다요!

 

 

봐주셔서 감사합니다!
질문이나 수정되어야 할 부분이 있다면 댓글로 남겨주세요!