백준 문제 풀이가 이해가 안됩니다.

Question

https://www.acmicpc.net/problem/2231문제를 간략하게 요약하자면ex 198 &#61;> 198 &#43; 1 &#43; 9 &#43; 8 &#61; 216 같은 로직이 있을떄216을 N, 198을 K라고 한다. N을 입력했을때 K의 최소값을 구하는 문제입니다.문제자체는 금방 풀었습니다.다만 제거 푼것보다 좀 더 효율적인 알고리즘이 있어서 이해해 보려고 했는데 도저히 이해가 안됩니다.https://st-lab.tistory.com/98 에 자세하게 적혀있습니다어떤 임의의 수 N이 들어올 때, 해당 수 N 은 K &#43; K의 각 자릿수 합이다.예로들어 네자릿수 정수 N 이 들어오면 해당 N 을 만드는 생성자는 임의의 K &#43; K의 각 자릿수가 되는 것이다.즉, 수식으로 보면 다음과 같다.N(4) &#61; K &#43; k1 &#43; k2 &#43; k3 &#43; k4그리고 이항을 하면 다음과 같다.N(4) - (k1 &#43; k2 &#43; k3 &#43; k4) &#61; K즉, 네자릿수 N 의 각 자릿수의 합이 최대일 때는 언제인가?9 &#43; 9 &#43; 9 &#43; 9 일 것이다.즉, 우리는 입력받은 정수 N 에 대하여 자릿수의 길이만큼 9를 빼주면 된다.그 미만의 수는 생성자가 될 수 없다는 것은 자명하다는 것이다.정리하자면N - (9 × K의 길이) 부터 탐색하여 N 까지만 탐색하면 된다.왜 각 자릿수의 합의 최대값을 빼는건지 이해가 안됩니다. K가 정해지지 않아서 k가 몇자리 숫자인지도 모르는데 왜 N의 길이*9를 빼는것이며, 왜 곱하기 9를 하는 건지 이해가 되지 않습니다.

KJS2020 · Answer

모든 경우의 수를 탐색할 필요없이,각 자리수의 최대값이 9이기때문에 N의 길이*9를 빼는겁니다.

코린이듈리 · Answer

해설을 그대로 이해하면 될것 같습니다.만약 N이 최대값인 100000이면 100000 - 9 - 9 - 9 - 9 - 9 - 9 = 9994699946부터만 탐색을 해 보면 됩니다.왜냐하면 6자리 숫자의 최대값은 999999 이기 때문입니다.이 미만의 값은 절대 생성자가 될 수 없습니다.

amiwho · Answer

질문자님이 혼동하신건 올리신 링크에서 N - (9 × K의 길이) 이것때문거같은데N-(9*n의길이)가 맞습니다 당연히 k를 모르는 상태인데 쓸 수 없죠제가 이해한건 이렇습니다k의 길이는 무조건 n의 길이거나, n-1의 길이겠죠?n의 길이 == k의 길이 => 각자리수를 다 더했을때 나올수있는 최댓값이 n-9*n의길이n의 길이-1 == k의 길이 => 위처럼 n의길이 계산했을때 더 작은 수가 나오므로 상관X (무조건 그보다 큰 수중에 존재할거임)

백준 문제 풀이가 이해가 안됩니다.

3개의 답변

기술 목록