취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 11999번 문제인 Milk Pails (Bronze)이다.
문제는 아래 링크를 확인하자.

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

양의 정수 K에 대하여 정확히 K만큼의 우유를 통에 채울 수 있다면 마지막으로 우유를 붓기 전에는 정확히 K-X 또는 K-Y만큼의 우유가 통에 채워져있었어야 함을 관찰하자.

위의 관찰을 이용하면, 0부터 모든 음이 아닌 정수를 차례로 보면서 현재 정수만큼의 우유를 정확히 채울 수 있다면 K+X, K+Y의 우유 또한 정확히 채울 수 있음을 기록해나가 문제를 해결할 수 있음을 알 수 있다.

위의 내용을 구현해 문제를 해결하자. 이 때, K+X 및 K+Y의 값은 M을 넘을 수 있음에 유의해 구현하자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int X, Y, M;
bool visited[2001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	visited[0] = 1;
	cin >> X >> Y >> M;

	for (int i = 0; i < M; i++) {
		if (visited[i]) visited[i + X] = visited[i + Y] = 1;
	}

	for (int i = M; i > -1; i--) {
		if (visited[i]) {
			cout << i;
			break;
		}
	}
}