이 문제에서는 세 개의 숫자 X, Y, N이 주어지며, N은 탐색 대상이 되는 범위 [1, N]을 정의합니다. 목표는 1부터 N 사이의 숫자 중에서 오직 X와 Y만을 원하는 횟수만큼 반복해 더하여 만들 수 있는 숫자가 총 몇 개인지 찾아내는 것입니다.
예를 들어 X=2, Y=3이라고 가정해 보겠습니다. 숫자 6은 2를 세 번 더한 값(2+2+2)이 될 수도 있고, 3을 두 번 더한 값(3+3)이 될 수도 있습니다. 마찬가지로 7은 2를 두 번, 3을 한 번 더한 값(2+2+3)으로 표현할 수 있습니다.
해결 방법은 의외로 단순합니다. 1부터 N까지의 각 숫자에서 X 또는 Y를 계속 빼 나가면 됩니다. 그 과정에서 최종적으로 숫자가 0으로 줄어든다면, 그 숫자는 X와 Y의 조합으로 만들 수 있다는 뜻이므로 카운트를 하나 증가시킵니다.
구체적인 예시를 통해 살펴보겠습니다.
입력 예시 1
N=10, X=4, Y=3
출력
X와 Y만으로 만들 수 있는 숫자의 총 개수: 7
설명
3과 4만으로 만들 수 있는 숫자:
3, 4, 6(3+3), 7(3+4), 8(4+4), 9(3+3+3), 10(3+3+4)
입력 예시 2
N=10, X=5, Y=4
출력
X와 Y만으로 만들 수 있는 숫자의 총 개수: 5
설명
4와 5만으로 만들 수 있는 숫자:
4, 5, 8(4+4), 9(4+5), 10(5+5)
알고리즘 접근 방법
아래 프로그램에 적용된 접근 방식은 다음과 같습니다.
- 세 개의 정수 X, Y, N을 입력받습니다.
- 함수 constructNums(int n, int x, int y)는 x와 y만으로 만들 수 있는 숫자의 개수를 반환합니다.
- 조건을 만족하는 숫자의 개수를 저장할 변수 count를 0으로 초기화합니다.
- for 루프를 이용해 i=1부터 i<=n까지 범위의 숫자를 하나씩 순회합니다.
- 각 숫자 num=i에 대해 while 루프를 돌며 num>0인 동안 아래 과정을 반복합니다.
- num이 x로 나누어떨어지고(num % x == 0) 0이 아니라면 x를 계속해서 뺍니다.
- num이 y로 나누어떨어지고(num % y == 0) 0이 아니라면 y를 계속해서 뺍니다.
- 위 과정 후에도 num이 x, y 어느 쪽으로도 나누어떨어지지 않으면서 x와 y보다 모두 크다면, x와 y를 한 번에 뺍니다.
- 바깥쪽 while 루프가 종료된 시점에 num이 0이라면, 그 숫자는 x, y 또는 둘 다의 조합으로 만들 수 있다는 의미이므로 count를 증가시킵니다.
- 모든 루프가 끝나면 count에는 조건을 만족하는 숫자의 총개수가 담기게 됩니다.
- 마지막으로 count를 결과값으로 반환합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
int constructNums(int n, int x, int y){
int count = 0;
for (int i = 1; i <= n; i++) {
int num = i;
while(num > 0){
while((num % x) == 0 && num != 0)
num -= x;
while((num % y) == 0 && num != 0)
num -= y;
if (num > x && num > y)
num = num - x - y;
else
break;
}
if (num == 0)
count++;
}
return count;
}
int main(){
int N = 20;
int X = 5, Y = 4;
cout << "X와 Y만으로 만들 수 있는 숫자의 총 개수:" << constructNums(N, X, Y);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
X와 Y만으로 만들 수 있는 숫자의 총 개수: 14
복잡도 분석 및 추가 팁
각 숫자마다 뺄셈 연산을 반복하므로, 위 구현의 전체 시간 복잡도는 대략 O(N² / min(X, Y)) 수준입니다. 따라서 N이 매우 커지면 비효율적일 수 있습니다.
이런 경우에는 동적 계획법(DP)을 활용하면 O(N) 시간에 문제를 해결할 수 있습니다. dp[0] = true로 초기화한 뒤, "i를 X와 Y로 만들 수 있는가"를 뜻하는 dp[i] = dp[i-X] || dp[i-Y] 점화식을 1부터 N까지 적용하고, true인 dp 값의 개수를 세면 됩니다. 이는 잘 알려진 '동전 문제(Coin Problem)' 유형과 동일한 구조입니다.