본문으로 건너뛰기
실습하기

1, 2, 3 더하기 해설

주어진 숫자 n을 1, 2, 3의 합으로 만드는 모든 경우의 수를 구하는 문제입니다.

이 함수는 동적 프로그래밍의 타뷸레이션 방식을 사용합니다.

타뷸레이션은 계산 결과를 테이블에 저장하고, 이후의 계산에서 이전에 계산된 값을 재사용하는 방식입니다.


함수 구현​

  1. 기본 경우 처리:

    • n < 3인 경우, n을 그대로 반환합니다. n이 1이나 2일 때 가능한 경우의 수는 각각 1과 2입니다.

    • n == 3인 경우, 경우의 수는 4이므로 4를 반환합니다.

  2. 타뷸레이션을 위한 배열 초기화:

    • dp 배열을 [0, 1, 2, 4]로 초기화합니다. 여기서 dp[i]는 n=i일 때의 경우의 수를 저장합니다.

  3. 동적 프로그래밍으로 경우의 수 계산:

    • 4부터 n까지의 각 숫자에 대해, dp[i]는 dp[i - 1], dp[i - 2], dp[i - 3]의 합으로 업데이트됩니다. 이는 n=i를 만드는 경우의 수가 n=i-1, n=i-2, n=i-3를 만드는 경우의 수의 합과 같음을 의미합니다.

모범 답안
def solution(n):
    # 기본 경우 처리
    if n < 3:
        return n
    if n == 3:
        return 4

    # 타뷸레이션을 위한 배열 초기화
    dp = [0, 1, 2, 4]

    # 동적 프로그래밍으로 경우의 수 계산
    for i in range(4, n + 1):
        dp.append(dp[i - 1] + dp[i - 2] + dp[i - 3])

    return dp[n]

사용 예시​

입출력 예시
print(solution(4))  # 출력: 7

solution(4)를 호출하면, 4를

만드는 경우의 수는 다음과 같습니다:

  1. 1 + 1 + 1 + 1
  2. 1 + 1 + 2
  3. 1 + 2 + 1
  4. 2 + 1 + 1
  5. 2 + 2
  6. 1 + 3
  7. 3 + 1

따라서 총 7가지 방법이 있으며, 이는 함수가 올바르게 7을 반환함을 나타냅니다.

다음 내용이 궁금하다면?

코드프렌즈 PLUS 멤버십 가입 or 강의를 등록해 주세요!