백준 2231번 : 분해합

문제 접근

---

1. 문제 설명에 나온 개념을 정리했다.
   
     문제에서 말하는 생성자란 무엇인지, 분해합이란 무엇인지, 내 나름대로 간단하게 정리했다.
   
   
2. 최악의 케이스를 상정해 봤다.
   
     1부터 최대 입력 값인 100만까지 하나하나 확인해 본다고 하면 시간 복잡도는 O(n)이다. 최악의 경우, 입력이 100만이라고 하더라도 제한 시간 안에 가능하다.
   
   
3. 그래도 시간을 더 줄일 수 있는 방법이 있나 생각해 봤다.
   
     최대 입력 값은 100만이다. 각 자릿수의 합이 가질 수 있는 최댓값은 N이 999,999일 때 각 자릿수의 합인 54이다. 따라서 N이 55 이상일 때, N-54 미만의 자연수가 만드는 분해합은 절대 N이 될 수 없다고 판단했다. 최종적으로는 N1과 N-54 중에 큰 값부터 N까지만 확인하도록 해서 시간을 조금이나마 아껴봤다.
   
     실제로 AC를 받은 사람들의 채점 결과를 확인해 보니 평균적으로 0ms~16ms까지 다양했는데, 내가 제출한 코드는 0ms로 비교적 빠른 편이었다.

 

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

1929번: 소수 구하기

 

 

 

문제 코드

---

#include <iostream>
#include <algorithm>

using namespace std;

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, decomposition, tmp, check_ans;

	cin >> N;

	check_ans = max(1, N - 54);
	decomposition = 0;

	for (; check_ans < N; ++check_ans)
	{
		decomposition = check_ans;
		tmp = check_ans;

		while (tmp / 10 != 0)
		{
			decomposition += tmp % 10;
			tmp /= 10;
		}

		decomposition += tmp % 10;

		if (decomposition == N)
		{
			cout << check_ans << '\n';
			break;
		}
	}

	if(decomposition != N)
		cout << "0\n";

	return 0;
}

 

 

 

느낀 점

---

    반쯤 뇌 빼고 코딩하는 것도 좋지만, 효과적인 회복을 위해서는 슬슬 골드 문제도 풀어봐야 될 것 같다. 지금까지는 단순 구현을 위한 문제였다면, 이제는 알고리즘을 위한 문제를 풀어보자.

 

1. Edge case를 한 번씩 확인해 보자.
   
     처음에 WA를 받아서 뭐가 문제인지 고민해 보다가, edge case를 넣어 확인해 봤다. 최솟값인 1과 최댓값이 100만을 넣어봤는데, 잘못된 출력이 나왔다. 생성자가 없는 경우 0을 출력한다는 조건을 생각 안 하고 코딩을 했었다.
   
     빠르게 edge case를 확인해서 해결할 수 있었다.
   
   
2. 조건을 잘 확인하자.
   
     예전에도 그랬지만, 문제를 꼼꼼히 본다면서 조건을 하나씩 놓치는 경우가 종종 있는 것 같다. 늘 조건을 침착하게 하나씩 확인하도록 하자.

 

    아! 추가로, check_ans와 decomposition의 경우는 조건문 안에서 초기화를 하니 'using uninitialized memory' 에러가 나와서 조건문 밖에서 초기화를 해놨다. 이런 부분은 생각을 못해서 그냥 임시방편으로 밖으로 빼놓긴 했는데, 뭔가 이쁘지가 않다.

    다음에는 변수가 사용되는 영역을 구분해서 선언해보는 것도 괜찮을 것 같다는 생각이 든다.