반응형
2231
-
BOJ) 분해합알고리즘/백준 2020. 7. 21. 15:03
분해합 2231번: 분해합 문제 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+ www.acmicpc.net 풀이 어떤 자연수 M과 N이 있을 때, M과 M의 각 자릿수 합이 N이되는 수의 최소값을 구하는 문제다. 범위를 어떻게 줄일지 생각이 나지 않아서, 일단은 DFS로 모든 경우의 수를 만들어서 검증했다. 자릿수 만큼 숫자를 만들고, 문제의 조건에 맞다면 최소값을 최신화해줬다. 메모리와 시간이 너무 보기 싫었다. 범위를 어떻게하면 줄일 수 있을지 생각하다가, 주어진 숫자의 각 자릿수가 9로만 이루어진 경우가 해당 자릿수에서 나올 수 ..