백준 4673 셀프 넘버 JAVA

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

4673번: 셀프 넘버

---

 

☆ 문제

 

○ 주의 사항

1. 1부터 10000까지 검사하면 되는 것이기에 new line으로 1부터 10000까지만 검사하면 된다.

 

★ 풀이

먼저 어떤 수 n이 생성할 수 있는 수를 d(n)이라고 한다면 결국엔 1 부터 10000까지 d(n) 될 수 없는 수들만 찾으면 된다.

문제 속에서 주어져있는 1, 3, 5, 7, 9 . . . . 등등의 수들은 절대로 어떤 생성자들로부터 만들어진 수가 될 수가 없다.

예) 2는 1이라는 생성자가 만들 수 있는 수, 4는 2라는 생성자가 만들 수 있는 수, 6은 3이라는 생성자가 만들 수 있는 수들 이지만,

1은 어떠한 생성자도 만들 수 없는 수, 3도 마찬가지로 어떠한 생성자로도 만들 수 없는 수로 이러한 수들을 셀프 넘버(Self Number)

라고 말하는 것이다.

 

그러면 먼저 어떠한 수 n을 매개변수로 하는 함수를 만들어서 그 n으로 만들 수 있는 수를 반환하여 1부터 10000까지의 수에서 제외한다면

제외되고 남은 수들이 셀프 넘버(Self Number)로 남는 것이다. 예를 들어서 n으로 1이라는 값이 매개변수로 들어와서 2라는 값으로 반환된다면 2라는 값은 1에서 부터 10000까지의 수에서 제외시키고 이런식으로 1부터 10000까지의 매개변수를 처리해주는 함수가 있다면 풀릴 수 있는 문제라는 것이다.

 

천천히 생각해보면 d(n)은 n의 각 자리 수를 더해서 만들어진 값이다. 

즉 2는 1의 1의 자리수인 1이 더해져 1 + 1 = 2 가 된 것이고

4는 2의 1의 자리수인 2가 더해져 2 + 2 = 4 가 된 것이다. 

이러한 알고리즘을 분석해서 코드를 작성해보면

 

public static int d(int n) {
		
		int sum = n;
		
		// n이 0이 되면 그때의 sum값 출력.
		while(n != 0) {
			// sum에 n을 10으로 나눈 나머지의 값 즉, 자리 수를 계속해서 더해주는 것.
			sum = sum + (n % 10);
			// 각 자리를 더해주기 위해 자리수를 하나씩 날려준다.
			n = (n / 10);
		}
		return sum;
	
		
	}
}

 

이렇게 표현할 수 있을 것 같다. 

 

이제는 Main 클래스에서 d(n)을 활용하여 1부터 10000까지의 수를 판별해보자.

 

 

public class Main {
	public static void main(String[] args) {
		
		 
		boolean[] check = new boolean[10001];
		
		for(int i = 1; i < check.length; i++) {
			
			// 1부터 10000까지의 수를 a 값에 넣어봄. return값으로 나오는 수는 
			// 우리가 원하지 않는 수
			
			int a = d(i);
			if(a < 10001) {
				check[a] = true;
			}
		}
		
		StringBuilder sb = new StringBuilder();
		
		// 만약 check[i] 번째의 배열이 false 값이라면 우리가 원하는 값이기 때문에
		// sb에 저장 후 sb출력. . . . 
		for(int i = 1; i < 10001; i++) {
			if(!check[i]) {
				sb.append(i).append("\n");
			}
		}
		
		System.out.println(sb);
	}

 

---

○ 마무리

 

많이 어려웠다. 셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다는데, 도대체 왜 붙힌걸까.. 

1시간 가량의 시간을 풀어보려고 오기를 부려가면서 도전했지만, 결국 혼자의 힘으로 푸는 것은 실패 . . . . .

구글링을 통해 답을 확인한 결과 . . . . . . 진짜 내가 짜고 있는 코드는 쓰래기 코드고, 이런 코드가 진짜 아름다운 코드라는 걸 다시

한번 느꼈다..  이렇게 아름답게 코드를 짤 수 있구나 . . . 라고 새삼 느껴버렸다..