파이썬으로 색타일로 덮을 수 있는 블록 수를 구하는 프로그램

문제 소개

길 위에 일렬로 놓인 블록이 있고, 한 작업자가 이 블록들에 색타일을 붙이고 있다고 가정해 보겠습니다. 작업자는 블록 번호가 4 또는 2로 나누어떨어지면서 42로는 나누어떨어지지 않는 경우에만 그 블록에 색타일을 붙입니다. 이때 작업자가 k개의 색타일을 가지고 시작한다면, 최대 몇 번째 블록까지 덮을 수 있는지 구하는 것이 이 프로그램의 목표입니다.

예를 들어 입력이 k = 16이라면 출력은 32가 됩니다. 2, 4, 6, ..., 32처럼 짝수 번호의 블록에 차례대로 타일을 붙였을 때, 16번째 타일이 32번 블록에 놓이기 때문입니다.

풀이 접근 방식

이 문제는 숫자의 규칙성만 파악하면 반복문 없이 간단한 수식으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

1부터 42까지의 범위에는 짝수가 총 21개 있지만, 42 자체는 타일 대상에서 제외되므로 실제로 타일이 붙는 블록은 정확히 20개입니다.
즉, 20개의 타일을 사용할 때마다 블록 42개 분량의 구간이 하나씩 진행됩니다.
따라서 k를 20으로 나눈 몫과 나머지를 이용하면 최종 블록 번호를 곧바로 계산할 수 있습니다.

단계별 풀이 과정

MOD = 10^9 + 7 로 설정합니다.
quotient := k를 20으로 나눈 몫(내림값)
remainder := k mod 20
remainder가 0과 같다면 ((42 × quotient − 2) mod MOD)를 반환합니다.
그렇지 않다면 ((42 × quotient + 2 × remainder) mod MOD)를 반환합니다.

나머지가 0일 때 2를 빼는 이유는, 해당 사이클의 마지막 블록 번호가 42의 배수라서 타일 대상에서 제외되기 때문입니다. 따라서 마지막으로 덮이는 블록은 그보다 2만큼 앞선 위치가 됩니다.

예제 구현

아래의 파이썬 코드를 통해 더 잘 이해해 보겠습니다.

def solve(k):
   MOD = 10**9 + 7
   quotient = k // 20
   remainder = k % 20
   if remainder == 0:
      return ((42 * quotient - 2) % MOD)
   else:
      return ((42 * quotient + 2 * remainder) % MOD)

print(solve(16))