[백준] 16456 하와와 대학생쨩 하와이로 가는 거시와요~

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

문제 이해

문제 요약

• 섬의 배치: 하와이 열도는 일렬로 배치된 n개의 섬으로 구성되어 있습니다.
• 여행 규칙:
  1. 다음 섬으로 이동: 현재 섬을 보고 바로 다음 섬 (i+1)으로 이동할 수 있습니다.
  2. 한 섬을 건너뛰고 이동: 현재 섬을 보고 한 섬을 건너뛰고 다음 섬 (i+2)으로 이동할 수 있습니다.
  3. 이전 섬으로 이동: 현재 섬을 보고 이전 섬 (i-1)으로 이동할 수 있습니다.
• 추가 조건:
  • 모든 섬을 한 번씩만 방문: 한 번 방문한 섬을 다시 방문할 수 없습니다.
  • 여행 시작점: 반드시 첫 번째 섬 (1번)에서 시작해야 합니다.
• 목표: 라가가 하와이 열도의 모든 섬을 방문할 수 있는 여행 방법의 수를 구합니다.
• 출력 조건:
  • 모든 섬을 방문할 수 있는 경우: 1을 출력하고, 이어서 각 초등학교별로 짝의 수를 출력합니다.
  • 불가능한 경우: 0을 출력합니다.

---

풀이 방법

동적 계획법(Dynamic Programming)을 이용한 접근

주어진 문제는 각 섬에 도달하는 방법의 수를 효율적으로 계산하기 위해 동적 계획법(DP)을 활용할 수 있습니다. DP는 복잡한 문제를 간단한 하위 문제로 나누어 해결하는 방식으로, 이 문제에서는 각 섬에 도달하는 방법의 수를 단계별로 계산합니다.

DP 배열 정의

• dp[i]: i번째 섬에 도달하는 여행 방법의 수를 저장합니다.
• 목표: dp[n]을 계산하여 출력합니다.

점화식 설정

섬 i에 도달하는 방법은 다음과 같이 두 가지 경우로 나눌 수 있습니다:

1. 이전 섬(i-1)에서 이동: i-1번째 섬에 도달한 모든 방법에서 i번째 섬으로 이동합니다.
2. i-3번째 섬에서 이동: i-3번째 섬에서 한 번의 건너뛰기를 통해 i번째 섬으로 이동합니다.

따라서, 점화식은 다음과 같이 설정됩니다:

dp[i] = dp[i-1] + dp[i-3]

초기 조건 설정

• dp[1] = 1: 첫 번째 섬은 시작점이므로 유일한 방법은 1입니다.
• dp[2] = 1: 두 번째 섬으로 이동하는 유일한 방법은 1 -> 2입니다.
• dp[3] = 2: 세 번째 섬으로 가는 방법은 두 가지가 있습니다:
  1. 1 -> 2 -> 3
  2. 1 -> 3

최종 구현

• 범위: 1 ≤ n ≤ 50,000이므로, 효율적인 계산을 위해 반복문을 사용합니다.
• 모듈러 연산: 결과가 매우 커질 수 있으므로, 각 단계에서 1,000,000,009로 나눈 나머지를 저장합니다.

# 동적 계획법을 이용한 여행 방법 계산

MOD = 1000000009  # 모듈러 값

def main():
    import sys
    input = sys.stdin.readline

    N = int(input())  # 섬의 개수
    dp = [0] * (N + 4)  # 안전하게 인덱스 범위 설정
    dp[1] = 1  # 첫 번째 섬에 도달하는 방법은 1가지

    if N >= 2:
        dp[2] = 1  # 두 번째 섬에 도달하는 방법은 1가지

    if N >= 3:
        dp[3] = 2  # 세 번째 섬에 도달하는 방법은 2가지

    for i in range(4, N + 1):
        dp[i] = (dp[i - 1] + dp[i - 3]) % MOD  # 점화식 적용

    print(dp[N])  # 결과 출력

if __name__ == "__main__":
    main()

코드 분석

1. 변수 및 배열 초기화

MOD = 1000000009  # 모듈러 값

N = int(input())  # 섬의 개수
dp = [0] * (N + 4)  # DP 배열 초기화
dp[1] = 1  # 첫 번째 섬 도달 방법

• MOD: 결과가 클 수 있으므로, 모든 계산은 1,000,000,009로 나눈 나머지를 취합니다.
• N: 섬의 총 개수를 입력받습니다.
• dp 배열: 섬의 개수 N에 맞게 크기를 설정합니다. 인덱스 초과를 방지하기 위해 N + 4로 설정합니다.
• 초기 조건: 첫 번째 섬은 시작점이므로 dp[1] = 1로 설정합니다.

2. 초기 조건 설정

if N >= 2:
    dp[2] = 1  # 두 번째 섬 도달 방법

if N >= 3:
    dp[3] = 2  # 세 번째 섬 도달 방법

• 두 번째 섬: 1 -> 2로만 이동 가능하므로 dp[2] = 1.
• 세 번째 섬: 두 가지 방법으로 이동 가능하므로 dp[3] = 2:
  1. 1 -> 2 -> 3
  2. 1 -> 3

3. 동적 계획법을 이용한 점화식 적용

for i in range(4, N + 1):
    dp[i] = (dp[i - 1] + dp[i - 3]) % MOD  # 점화식 적용

• 점화식: dp[i] = dp[i-1] + dp[i-3]
  • dp[i-1]: i-1번째 섬에 도달하는 모든 방법에서 i번째 섬으로 한 칸 이동.
  • dp[i-3]: i-3번째 섬에 도달하는 모든 방법에서 세 칸 이동 (i-3 -> i-2 -> i-1 -> i), 즉, 한 번의 건너뛰기 이동.
• 모듈러 연산: 각 단계에서 결과를 1,000,000,009로 나눈 나머지를 저장하여, 큰 수를 방지합니다.

4. 결과 출력

print(dp[N])  # 결과 출력

• dp[N]: N번째 섬에 도달하는 총 여행 방법의 수를 출력합니다.

---

시간 복잡도

계산 단계별 분석

1. 입력 및 배열 초기화:
   • 시간 복잡도: O(1)
   • 설명: 섬의 개수를 입력받고, DP 배열을 초기화하는 단계는 상수 시간 내에 완료됩니다.
2. 초기 조건 설정:
   • 시간 복잡도: O(1)
   • 설명: 첫 번째, 두 번째, 세 번째 섬에 대한 초기 조건을 설정하는 단계는 상수 시간 내에 완료됩니다.
3. 동적 계획법 적용 (반복문):
   • 시간 복잡도: O(N)
   • 설명: 4부터 N까지 반복문을 돌며 dp[i]를 계산합니다. 각 i에 대해 상수 시간 내에 계산이 이루어지므로 전체적으로 선형 시간입니다.
4. 결과 출력:
   • 시간 복잡도: O(1)
   • 설명: 최종 결과를 출력하는 단계는 상수 시간 내에 완료됩니다.

전체 시간 복잡도

• 총 합계: O(1) + O(1) + O(N) + O(1) = O(N)
• 설명: 섬의 개수 N에 비례하는 선형 시간 복잡도를 가집니다. N의 최대 값이 50,000이므로, 효율적으로 계산이 가능합니다.

---

공간 복잡도

계산 단계별 분석

1. DP 배열:
   • 공간 복잡도: O(N)
   • 설명: dp 배열은 N + 4 크기로 할당되며, 각 섬에 대한 방법의 수를 저장합니다.
2. 기타 변수:
   • 공간 복잡도: O(1)
   • 설명: 기타 변수들(예: MOD, i 등)은 상수 공간을 사용합니다.

전체 공간 복잡도

• 총 합계: O(N) + O(1) = O(N)
• 설명: 주로 DP 배열에 의해 선형 공간이 필요합니다. N의 최대 값이 50,000이므로, 메모리 사용도 효율적입니다.

---

알고리즘 및 자료구조 설명

알고리즘: 동적 계획법 (Dynamic Programming)

• 동적 계획법의 특징:
  • 재귀적 하위 문제 해결: 큰 문제를 작은 하위 문제로 나누어 해결합니다.
  • 메모이제이션: 이미 계산된 결과를 저장하여 중복 계산을 방지합니다.
  • 점화식 활용: 현재 상태를 이전 상태들로부터 유도합니다.
• 이 문제에서의 적용:
  • 상태 정의: dp[i]는 i번째 섬에 도달하는 모든 가능한 여행 방법의 수입니다.
  • 점화식 설정:

    css
    코드 복사
    dp[i] = dp[i-1] + dp[i-3]
    

    • 이는 i번째 섬에 도달하는 방법이 두 가지 경우로 나뉨을 의미합니다:
      1. 직접 이동: i-1번째 섬에서 i번째 섬으로 한 칸 이동.
      2. 건너뛰기 이동: i-3번째 섬에서 세 칸 이동하여 i번째 섬으로 도달.

자료구조: 배열 (List)

• dp 배열:
  • 역할: 각 섬에 도달하는 방법의 수를 저장.
  • 특징: 인덱스를 통해 각 섬의 상태에 빠르게 접근 가능.
  • 장점:
    • 효율적인 접근: O(1) 시간에 특정 인덱스에 접근 가능.
    • 간단한 구현: 동적 계획법의 상태 저장에 적합.

모듈러 연산

• 목적: 결과가 매우 커질 수 있으므로, 계산 과정에서 계속해서 1,000,000,009로 나눈 나머지를 취합니다.
• 방법:

   dp[i] = (dp[i - 1] + dp[i - 3]) % MOD
   

• 이는 각 단계에서의 결과를 제한된 크기로 유지하여, 오버플로우를 방지하고 원하는 형식으로 결과를 출력할 수 있게 합니다.

  참고
  https://hrothgar.tistory.com/99