Self-number

1. 문제

 

2. 문제 분석

위에서 셀프넘버를 구해야 한다고 했다.

그런데 문제의 예시에서 나왔다시피,

숫자 91과 100의 제네레이터는 101로 서로 같다.

위의 에시에서 보다시피, 중복되는 제네레이터를 기록해야 한다.

즉, 메모이제이션 기법을 써야하며, 배열로 두자.

그리고, 배열의 인덱스를 어떤 용도로 쓰냐면, 해당 정수의 제네레이터로 쓰자.

문제 풀이 방법은 2가지가 있는데, 둘 다 메모이제이션 기법을 쓰며,

해당정수의 각 자리수를 얻어내는 방법은 동일하다.

해당 정수의 각 자리수를 얻어내는 방법은 while문을 이용해서

10으로 나눈 나머지와 몫을 이용하면 쉽게 알 수 있다.

 

3. 자료 구조 정의

Array배열은 기록을 위한 배열이다. 즉, 중복을 막기위함이다.
배열의 길이가 왜이렇게 크냐라는 질문을 할 수 있는데,
배열의 인덱스가 어떤 용도인지 파악을 해야 하는데
예를 들어서 문제에 나와 있는 것처럼, 정수3에 대응하는 제네레이터 6,
정수91에 대응하는 제네레이터는 101이다.
즉, Array배열의 인덱스의 용도가 바로 제네레이터로 활용할 것이기 때문이다.

 

4. 구현

프로그램 실행결과

소스 파일

main.c

0.00MB

 

5. 다른 방식의 풀이

DT배열은 기록을 위한 배열이다.

0이면 기록이 되어 있지 않음을 의미하고 1이면 기록을 의미.

프로그램 실행결과

 

소스 파일

main.c

0.00MB