이 문제가 조금 글이 이상하게 적혀있어서 이해를 못해서 블로그 글을 찾는 사람이 많을 것 같아서
먼저 이렇게 문제 이해를 도와드리겠습니다.
[
2231번: 분해합
어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이
](http://acmicpc.net/problem/2231)
예시에서 245의 분해합이 256이라고 한다. 245 + 2 + 5 + 6이라서 256이다.
이 256을 분해합으로 가지는 가장 작은 수를 구하라는 것이 이 문제의 물음이다.
참고로 256을 입력으로 입력을 하면 245가 나온다.
글이 이해가 안되서.. 처음에는 분해합을 구하는 줄 알았다가 전혀 아닌거 같아서 다시 자세히 하나하나 읽어보니 알게 되었다.
그리고 이 문제 풀이에 대한 힌트를 드리겠습니다.
힌트? 인지는 정확하게 모르겠지만 백준을 풀면서 하도 시간 초과가 많이 나와서 항상 반복문의 수를 줄이거나 범위는 줄이는 생각을 많이 하였습니다.
여기서 범위를 줄이는 방법은 (분해합 수) - 9*(총자리수)입니다. 만약 위처럼 256을 분해합을 가지는 수를 구할 때 범위는 256-9*3<= 범위 <= 256 => 229<= 범위 <=256입니다.
그 이유는 3자리일 때 가장 큰 수는 999입니다. 그렇기에 9*(총자리수)를 빼면 범위가 나옵니다.
이러한 힌트를 가지고 코딩을 진행하면 이제 그 뒤는 쉽게 풀 수 있습니다.
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
int main()
{
int n;
scanf("%d", &n); //n이 246일때 분해합은 246 + 2 + 4+ 6 = 258이다. 수를 입력 받음.
//이때 246은 258의 생성자이다.
int count = 0; int m = n; //n과 m은 같다.
while (n != 0) {
count++; //자리수 카운트 -> 범위를 알기 위해서
n = n / 10;
}
int checkCount = 0; // sum == m이 있는지 확인하는 변수
int sum = 0; int i;
for (i = m - 9 * count; i <= m; i++) {
int j = i;
sum = j;
while (j != 0) {
sum = sum + j % 10;
j = j / 10;
}
if (sum == m) {
checkCount++;
break;
}
}
if (checkCount != 0) {
printf("%d", i);
}
else {
printf("0");
}
}
'백준 문제 풀이 & C++ 공부' 카테고리의 다른 글
백준 2751번 C/C++ (0) | 2021.02.15 |
---|---|
백준 2292번 C/C++ (0) | 2021.02.12 |
백준 2614번 C/C++ (0) | 2021.02.08 |
백준 10163번 C/C++ (0) | 2020.09.06 |
백준 9095번 C/C++ (0) | 2020.08.24 |