[ACM-ICPC][BOJ] 14954 - HAPPY NUMBER 문제풀이

안녕하세요

여행벌입니다.

오늘은 백준 14954번 ACM 2017 본선 D번 문제 풀이를 해보겠습니다.

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

---

문제는 '어떤 숫자가 주어졌을 때, HappyNumber인지 아닌지 구분해주는 알고리즘을 구현하라.' 입니다.

이 때, HappyNumber 란 숫자가 주어졌을 때, 각 자릿수의 제곱을 더해나가고 이 과정을 거쳐 최종적으로 1에 도달할 수 있는 수를 뜻합니다.

예를 들어,

3이란 숫자가 주어지면 19 -> 82 -> 68 -> 100 -> 1 로 HappyNumber인 것을 확인할 수 있습니다.

4라는 숫자는 4 -> 16 -> 37 -> 56 -> 61 -> 37 순환(Cycle) 고리가 생겨 UnHappyNumber인 것을 볼 수 있습니다.

따라서, 우리는 다음과 같이 알고리즘을 설계할 수 있습니다.

 

[알고리즘 설계]

1. 어떤 숫자가 주어졌을 때, 각 자릿수를 구하고 제곱해서 더한 값을 return 해주는 함수.

2. 각 자리수를 구하고 제곱해서 더해나가다가 순환(recycle) 고리가 생기는지 체크해주는 함수. 

3. 순환 고리가 생긴다면 UNHAPPY / 순환 고리가 생기지 않고 1이란 숫자가 나타나면 HAPPY 를 출력해주는 함수.

 

총 3가지 작업이 필요하다는 것을 확인할 수 있습니다.

설계한 알고리즘을 구현해보겠습니다.

#include<iostream>

using namespace std;

int nlist[10] = {};
int repeat[10000000] = {};

int divide(int);
bool check_repeat(int, int);

int main(void) {
	int ninput, count = 0;
	cin >> ninput;
	while (1) {
		repeat[count] = ninput;
		if (ninput == 1) {
			cout << "HAPPY";
			break;
		}
		if (check_repeat(ninput, count) || count == 9999999) {
			cout << "UNHAPPY";
			break;
		}
		ninput = divide(ninput);
		//cout << count << "번 째 : " << ninput << endl;
		count++;
	}
}

/* 자리수별로 자른다. */
/* 자리수별로 제곱해서 더한 값을 return해준다. */
int divide(int ninput) {
	/* 이 부분 예외처리 안해서 틀렸음.*/
	if (ninput < 10) {
		return ninput * ninput;
	}
	int out = 0;
	nlist[0] = ninput / 1000000000;
	nlist[1] = (ninput % 1000000000) / 100000000;
	nlist[2] = (ninput % 100000000) / 10000000;
	nlist[3] = (ninput % 10000000) / 1000000;
	nlist[4] = (ninput % 1000000) / 100000;
	nlist[5] = (ninput % 100000) / 10000;
	nlist[6] = (ninput % 10000) / 1000;
	nlist[7] = (ninput % 1000) / 100;
	nlist[8] = (ninput % 100) / 10;
	nlist[9] = (ninput % 10);
	for (int i = 0; i < 10; i++) {
		if (nlist[i] != 0)
			out += nlist[i] * nlist[i];
	}
	return out;
}

// 지금까지나왔던 값 중에서 현재 값이 있는지 없는지 확인한다.
bool check_repeat(int ninput, int count) {
	for(int i =0 ; i< count; i++){
        if(repeat[i] == ninput)
            return true;
    }
    return false;
}

각 자릿수를 구하는 divide 함수는 https://travelbeeee.tistory.com/4 기존의 포스팅 글을 참고하시면 될 것 같습니다. 

check_repeat 함수는 지금까지 결과로 나왔던 값들을 순회하며 공통된 값이 존재하면 순환(Cycle)고리가 형성된 것이므로 true 아니면 false를 return 해주는 함수입니다.

---

아마 2017 ACM-ICPC 예선에서 가장 쉬운 문제가 아닐까 싶습니다.

알고리즘 설계하기 굉장히 쉬웠고, 예외만 잘 잡아준다면 쉽게 풀 수 있는 문제인 것 같습니다.