[백준 11726 파이썬/python] 2 x n 타일링

2×n 타일링

문제

입력

출력

예제 입력 1

예제 출력 1

예제 입력 2

예제 출력 2

풀이

1)

2)

2×n 타일링

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	139665	53474	39544	36.175%

문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

예제 입력 1

2

예제 출력 1

2

예제 입력 2

9

예제 출력 2

55

풀이

1)

def tiling(n):
    dp = [0] * 1001
    dp[0] = 1
    dp[1] = 1

    for i in range(2, n + 1):
        dp[i] = (dp[i - 1] + dp[i - 2]) % 10007

    return dp[n]


n = int(input())
print(tiling(n))

• 풀이과정
  1. tiling이라는 함수를 정의합니다. 이 함수는 인자로 정수 n을 받습니다. 함수의 목적은 2×n 크기의 직사각형을 채우는 방법의 수를 계산하는 것입니다.
  2. 함수 내에서 길이가 1001인 dp 리스트를 생성하고, 모든 값을 0으로 초기화합니다. 이 리스트는 동적 프로그래밍에서 사용되며, 각 인덱스 i는 2×i 크기의 직사각형을 채우는 방법의 수를 저장하는 데 사용됩니다.
  3. dp[0]과 dp[1]의 값을 각각 1로 초기화합니다. 이것은 2×0 및 2×1 크기의 직사각형을 채우는 방법의 수가 각각 1개임을 의미합니다.
  4. for문을 사용하여 2부터 n까지 반복합니다. 반복문 내에서는 dp[i] 값을 계산합니다. 이 값은 이전의 dp[i-1] 값과 dp[i-2] 값을 더한 것입니다. 이 공식은 점화식에 따른 동적 프로그래밍 접근 방식을 사용하여 문제를 해결합니다.
  5. 계산된 dp[i] 값을 10007로 나눈 나머지를 저장합니다. 이렇게 함으로써, 모든 계산 과정에서 10007로 나눈 나머지를 유지하게 됩니다.
  6. 함수가 끝날 때, dp[n] 값을 반환합니다. 이 값은 2×n 크기의 직사각형을 채우는 방법의 수입니다.
  7. main 부분에서 사용자로부터 n 값을 입력받습니다. 이후, tiling(n) 함수를 호출하여 결과를 얻고 출력합니다. 출력 값은 2×n 크기의 직사각형을 채우는 방법의 수를 10007로 나눈 나머지입니다.

2)

n = int(input())
d = [0]*1001
d[0] = 1
d[1] = 1
for i in range(2, n+1):
    d[i] = d[i-1] + d[i-2]
    d[i] %= 10007
print(d[n])

• 풀이과정
  1. 사용자로부터 n 값을 입력받습니다. n은 직사각형의 가로 크기입니다.
  2. 길이가 1001인 d 리스트를 생성하고, 모든 값을 0으로 초기화합니다. 이 리스트는 동적 프로그래밍에서 사용되며, 각 인덱스 i는 2×i 크기의 직사각형을 채우는 방법의 수를 저장하는 데 사용됩니다.
  3. d[0]과 d[1]의 값을 각각 1로 초기화합니다. 이것은 2×0 및 2×1 크기의 직사각형을 채우는 방법의 수가 각각 1개임을 의미합니다.
  4. for문을 사용하여 2부터 n까지 반복합니다. 반복문 내에서는 d[i] 값을 계산합니다. 이 값은 이전의 d[i-1] 값과 d[i-2] 값을 더한 것입니다. 이 공식은 점화식에 따른 동적 프로그래밍 접근 방식을 사용하여 문제를 해결합니다.
  5. 계산된 d[i] 값을 10,007로 나눈 나머지를 저장합니다. 이렇게 함으로써, 모든 계산 과정에서 10,007로 나눈 나머지를 유지하게 됩니다.
  6. 반복문이 끝나면, d[n] 값을 출력합니다. 이 값은 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지입니다.

  이 코드는 주어진 문제를 효과적으로 해결하는 동적 프로그래밍 알고리즘을 구현한 것입니다. 이를 통해 2×n 크기의 직사각형을 채우는 방법의 수를 빠르게 계산할 수 있습니다.

Uploaded by N2T