[백준] 1038번 : 감소하는 수

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

 

 

💡 접근법

이전에 사전 문제를 풀었던게 생각나서 그 문제랑 비슷하게 풀었다 ( https://www.acmicpc.net/problem/1256 )

 

우선 이 문제를 두 단계로 분리하자면

1. 지금 내가 찾는 숫자가 어떤 범위에 있는지 와 2. 실제 숫자가 뭔지

를 찾는 두 단계로 나눠야 한다

 

1. 지금 내가 찾는 숫자가 어떤 범위에 있는지 찾기

기본적으로 한 숫자가 정해지면, 그 뒤의 숫자들은 이 앞자리 숫자에 종속이 된다

경우의 수들을 쭉 쓰다보면, 5421 라는 감소수는 4가 가장 앞자리인 숫자의 맨앞에 5를 더한 것과 같다

5가 가장 앞자리인 4자리 숫자들 중, 그 다음 수가 4___ 인 경우의 수는, 4가 가장 앞자리인 3자리 수와 같다

즉 DP 식으로 정리하자면

• 지금 몇자리수인지 i, 가장 앞자리 숫자가 뭔지 j 에 대해. k를 반복문으로 돌리면
• DP[i][j] = DP[i-1][k] 와 같다

 

조금 더럽지만.. 내가 찾을 때 끄적거린 기록

 

DP 식을 먼저 구해서 찾고자 하는 숫자가 몇자리 수의, 가장 맨 앞자리가 어떤 숫자인지 찾을 수 있다

 

2. 실제 숫자가 뭔지

가장 맨 앞자리가 뭔지 알았다면, 그 다음 숫자부터는 자릿수를 하나씩 줄여가면서 1번을 반복하면 된다

 

18번째 숫자를 찾고자 하는 경우,

2번째 자릿수가 4 인 숫자의 범위는 16~19 이기 때문에 여기서 자릿수를 내린다

 

1번째 자릿수가 0인 숫자의 범위는 16~16이기 때문에 스킵하고 증가시키고

1번째 자릿수가 1인 숫자의 범위는 17~17이기 때문에 스킵하고 증가시키고

1번째 자릿수가 2인 숫자의 범위는 18~18이기 때문에 찾는 숫자와 같으므로 정답을 출력한다

 

이 알고리즘을 코드로 구현하면 된다

 

• 숫자의 범위를 알았어도, 뒷자리가 다 채워지지 않았을 수 있으므로 그 경우도 체크해야 한다

 

➕ 짚고 넘어가기

 

🧪 테스트 케이스

입력	출력
1022	9876543210
1023	-1

 

---

✏️ 나의 풀이

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int DP[11][11]; // 자릿수 r 일때 앞자리 c인 경우의 수
int main() {
    int TargetNum;
    cin >> TargetNum;

    if (TargetNum == 0)
    {
        cout << 0 << "\n";
        return 0;
    }

    int MaxValue = 0;
    for (int i = 0;i < 10;i++)
    {
        DP[1][i] = 1;
    }

    for (int i = 2; i < 11;i++)
    {
        for (int j = 1; j < 10;j++)
        {
            for (int k = 0;k < j;k++)
            {
                DP[i][j] += DP[i - 1][k];
            }
        }
    }

    int Count = -1;
    long long Answer = 0;
    for (int i = 1;i < 11;i++)
    {
        for (int j = 0;j < 10;)
        {
            if (DP[i][j] == 0) 
            {
                j++;
                continue;
            }
            if (Count + DP[i][j] >= TargetNum)
            {
                //지금 앞자리에 대해 타겟이 안에 있으면 숫자찾기
                Answer = Answer * 10 + j;

                if (i == 1 && Count + DP[i][j] == TargetNum)
                {
                    //뒷자리수까지 다 채워졌는지 확인
                    cout << Answer << "\n";
                    return 0;
                }
                else
                {
                    i--;
                    j = 0;
                }
            }
            else
            {
                //없으면 다음으로 넘어가기
                Count += DP[i][j];
                j++;
            }
        }
    }

    cout << -1 << "\n";

    return 0;
}

 

✏️ 다른 사람의 풀이

 

실제 개수가 많지 않아서 단순 DFS로 풀어도 풀리는 문제였다

평상시였으면 백트래킹으로 먼저 생각했을 것 같은데, 이전에 DP로 풀었더니 생각이 이렇게 박혀버림..

 

 

---

 

코드 구현하다가 은근 시간을 많이 잡아먹었다

미리 생각 다 해놓고 시작해도 짜다보면 구현이 많이 막히는듯.. 구현 연습을 더 많이 해야한다