만들 수 있는 합을 상태로 표시하기

개수가 아니라 가능 여부를 저장해요

dp의 상태 의미와 계산 순서를 배웠어요. 이번에는 최소 비용 대신 합을 만들 수 있는지를 저장해요. reachable[amount]의 0은 아직 못 만듦, 1은 만들 수 있음을 뜻해요.

예제에서 크기 2 또는 3인 블록을 몇 개든 쓸 수 있어요. 아무것도 안 쓰면 합 0이므로 reachable[0]= 1이에요. 합 2는 0에 2를 더해 만들고 합 3은 0에 3을 더해 만들어요. 그림은 0에서 두 크기로 늘어나는 합이에요.

작은 합의 상태를 확인해요

크기 2·3으로 합 4를 만들려면 이전 합 2가 가능한지 보면 돼요. 합 5는 3 +2 또는 2 +3으로 가능해요. 합 1은 어느 이전 상태에서도 만들 수 없어요.

amount를 작은 순서로 계산해요. and는 두 조건이 모두 맞아야 참이에요. amount >= size and reachable[amount - size] == 1은 먼저 범위 검사에 통과한 경우만 이전 칸을 읽어요. 범위 검사 없이 음수 인덱스를 읽으면 Python에서는 뒤쪽 칸을 읽어 잘못된 상태를 쓸 수 있어요.

직접 풀어봐요

크기 first와 second 인 블록을 각각 0개 이상 반복해서 사용해요. 합 1~limit 중 만들 수 있는 서로 다른 합의 개수를 출력해요. 크기가 같아도 같은 합을 두 번 세지 않아요.

입력은 첫 줄 first, 둘째 줄 second(각 120), 셋째 줄 limit(0100)이에요. 합 0은 시작 상태지만 출력 개수에는 포함하지 않아요.

예시 1: first = 2, second = 3, limit = 6 → 5. 2·3·4·5·6이에요. 예시 2: first = 4, second = 6, limit = 10 → 4. 4·6·8·10이에요.

2
3
6

5

4
6
10

4