개요
필자는 백준 실버를 이 글을 쓰는 당일날 새벽에 달성했습니다.
마지막엔 실버 5 문제를 두개 풀고 승급했는데 솔직히 실버 5 문제도 너무 어려워서 중간에 껴있는
1193. 분수찾기, 1427. 소트인사이드 같은 날먹 문제만 빠르게 먹고 올라왔습니다.
저에겐 아직 실버 문제도 어렵기 때문에 지금부터 풀 실버 5 문제 중 제 맘에 드는걸 풀어서 올리려고 합니다.
아직 쫄보인 저에게 solved.ac에서 푼 사람수로 내림차 순 정렬했을때 가장 위에있던 문제인
4673. 셀프 넘버 문제가 눈에 들어왔습니다.
문제
셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다.
양의 정수 n이 주어졌을 때, 이 수를 시작해서 n, d(n), d(d(n)), d(d(d(n))), ...과 같은 무한 수열을 만들 수 있다.
예를 들어, 33으로 시작한다면 다음 수는 33 + 3 + 3 = 39이고, 그 다음 수는 39 + 3 + 9 = 51, 다음 수는 51 + 5 + 1 = 57이다. 이런식으로 다음과 같은 수열을 만들 수 있다.
33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141, ...
n을 d(n)의 생성자라고 한다. 위의 수열에서 33은 39의 생성자이고, 39는 51의 생성자, 51은 57의 생성자이다. 생성자가 한 개보다 많은 경우도 있다. 예를 들어, 101은 생성자가 2개(91과 100) 있다.
생성자가 없는 숫자를 셀프 넘버라고 한다. 100보다 작은 셀프 넘버는 총 13개가 있다. 1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, 97
10000보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 출력하는 프로그램을 작성하시오.
...라고 하는데 일단 다른 문제처럼 이해가 안가는건 아니니까 양호한 편입니다.
풀이
제일 먼저 생각난건 1부터 10000까지 들어있는 int 배열을 만들어서 모든 숫자에 d(n)을 돌려서 나온것들을 배열에서 지워나가는 거였습니다.
...솔직히 이건 구현할 수는 있어도 작업량이 개 또라이 같을 것 같았습니다.
제가 최적화에 진짜 단 하나도 조예가 없기 때문에 이 방법이 메모리를 생각만큼 많이 잡아먹는지에 대한 여부는 모르겠지만 별로 맘에드는 방법은 아니였어요.
그래서 생각해낸 방법이 함수와 역함수였습니다.
n을 먹고 d(n)을 뱉어내는건 일반 함수고 d(n)을 먹고 n을 뱉어내는건 역함수 아닌가?
그러면 d(n)을 먹었을때 뱉어내는게 없으면 그건 셀프 넘버겠네?
오? 발상 좀 천재 같은데?
라는 자뻑으로 풀이를 시작했습니다.
일단 d(n)이라고 하는 함수를 먼저 구현해봅시다.
public static int D(int n)
{
int sum = n;
while(n != 0)
{
sum += n % 10;
n /= 10;
}
return sum;
}
n을 넣으면 n + (n의 각 자릿 수) 를 리턴해주는 D 함수입니다.
그리고... 이제 역함수를 구현할 차례입니다.
계산을 역방향으로 해봤자 처음 들어온 n을 모르기 때문에 반복문을 몇번 돌아야 하는지 조차 알 수 없어요.
물론 유추할 수는 있습니다. 들어온 D(n)은 n과 아무리 차이나봤자 단 한자리 수 차이일 뿐입니다.
하지만 거기까지. 수학적으로 완벽한 역함수를 만들어내는건 저의 뇌론 불가능합니다.
그러니 들어간 n을 찾기 위해 1부터 10000까지 싹다 대입해보는 방법을 채택할 수 있겠죠.
public static int RevD(int dn)
{
for(int i = 0; i < 10001; i++)
{
if (D(i) == dn) return i;
}
return -1;
}
...이이이이런식으로 말입니다.
여기서 이제 -1이 나오는 놈들은 생성자가 없는애들 입니다.
그렇게 되면
Console.WriteLine(D(13)); // 출력결과 17
Console.WriteLine(RevD(D(13))); // 출력결과 13
Console.WriteLine(RevD(1))); // 출력결과 -1
아주 작동을 잘하는 모습을 보여줍니다.
이제 한번 구현 해봅시다.
for (int i = 0; i < 10001; i++)
{
if (RevD(i) == -1) Console.WriteLine(i);
}
그냥 1부터 10000까지 도는 for문 하나만 만들면 끝입니다.
결과
와~~
1트만에 눈물의 합격!!
마치는 말
이 글을 다 풀고나서 적은게 아니라 적으면서 실시간으로 풀었는데 이러니까 문제가 몇배는 쉬운 느낌입니다.
살짝 수학을 이면지에 적으면서 푸는 느낌이랄까...
골드 가는 그 날까지 달리겟습니다.
코드 전문
using System;
public static class Program
{
public static void Main(string[] args)
{
for (int i = 0; i < 10001; i++)
{
if (RevD(i) == -1) Console.WriteLine(i);
}
}
public static int D(int n)
{
int sum = n;
while(n != 0)
{
sum += n % 10;
n /= 10;
}
return sum;
}
public static int RevD(int dn)
{
for(int i = 0; i < 10001; i++)
{
if (D(i) == dn) return i;
}
return -1;
}
}
수고링