길이가 각각 sizes[0], sizes[1]인 두 종류의 도장을 이어 찍어요. 첫 도장은 어느 종류든 가능하지만 바로 전에 쓴 종류와 같은 도장은 연속해서 쓸 수 없어요. 두 길이가 같아도 종류는 달라요. 한 개 이상 찍어서 만든 총길이 중 limit 이하인 서로 다른 길이 수를 구해요. 같은 총길이를 여러 방법으로 만들어도 한 번만 세요.
solution(sizes, limit)가 길이 수를 반환하도록 빈칸을 채워 주세요. 제공된 seen[amount][last]는 총길이 amount를 마지막 종류 last로 만들 수 있는지를 나타내요.
매개변수와 반환값
- sizes의 길이는 2이고 각 길이는 1
20, limit는 0400이에요. - 아무 도장도 찍지 않은 길이 0은 세지 않아요.
- 반환값은 만들 수 있는 서로 다른 양의 길이 수예요.
예시
sizes = [2, 3],limit = 10이면 결과는6이에요.sizes = [4, 4],limit = 12이면 결과는3이에요.
실행용 입출력
첫 줄에 size0 size1 limit를 입력하고 결과 하나를 출력해요.
예시 입력
2 3 10
예상 결과
6
예시 입력
4 4 12
예상 결과
3
핵심 개념
dp-1d: seen은 이미 만들 수 있는 길이의 상태를 저장해요. 같은 총길이라도 마지막 종류가 다르면 다음에 쓸 수 있는 도장이 달라요.array-1d: last가 0·1인 두 상태를 각 길이에 붙여요.[[False, False] for _ in range(limit + 1)]은 길이마다 독립된 행을 만들어요.conditionals: 길이가 증가하는 전이만 있어 작은 길이부터 확인할 수 있어요.or또는any(...)는 마지막 종류 중 하나라도 도달할 수 있는지 확인해요.
continue는 현재 반복의 나머지를 건너뛰고 다음 반복으로 가요. bool 값 True·False는 가능·불가능을 표현해요. 두 종류의 길이가 같아도 종류 인덱스는 따로 유지해요.
입력 하네스의 input()은 한 줄의 문자열을 읽고, .split()은 공백으로 항목을 나눠요. map(int, ...)는 각 항목을 정수로 바꾸고 list(...)는 그 결과를 리스트로 모아요. range(n)은 0부터 n-1까지 반복해요. 하네스는 함수 호출을 위한 자체 연결이며 풀이의 반환 계약과 구분해요.