[백준/Python] 15988번 - 1, 2, 3 더하기 3

2023. 9. 29. 16:20·Algorithm/BaekJoon
import sys
input = sys.stdin.readline

DIV = 1000000009

dp = [1, 2, 4, 7]
for _ in range(int(input())):
  # 방법의 총 수 dp, 순서 바꾸는 것도 포함이네..
  n = int(input())

  for i in range(len(dp), n):
    # 알아서 1, 2, 3이 각각 들어갈 것 -> 겹치는게 없음
    dp.append((dp[i-1] + dp[i-2] + dp[i-3]) % DIV)

  print(dp[n-1])

점화식은 발견 했는데 시간 초과, 메모리 초과를 어떻게 해결해야할지 생각해내는게 어려웠다.

이를 해결한 방법은 다음과 같다.

 

1. 모든 테스트케이스는 같은 DP 값을 가지니 DP를 global 하게 사용

2. 이미 있는 dp 값을 재활용하기 위해 for문 start가 len(dp)로 들어감

3. dp[3]까지 값을 미리 넣어놓기

+) 참고로 숫자는 그때 그때 나눠서 넣어야한다! DP 값에는 나머지 값이 들어가야한다는 의미!

 

 

시간 복잡도

n은 양수, 1,000,000 보다 작거나 같다

테스트 케이스가 몇개인지는 모르곘으나 한 테스트 케이스의 시간 복잡도는

for문: O(n)

=> O(n)

 

'Algorithm > BaekJoon' 카테고리의 다른 글

[백준/Python] 7785번 - 회사에 있는 사람  (0) 2023.09.30
[백준/Python] 2164번 - 카드 2  (0) 2023.09.30
[백준/Python] 2748번 - 피보나치 수 2  (0) 2023.09.29
[백준/Python] 1600번 - 말이 되고픈 원숭이  (0) 2023.09.10
[백준/Python] 13549번-숨바꼭질 3  (0) 2023.09.10
'Algorithm/BaekJoon' 카테고리의 다른 글
  • [백준/Python] 7785번 - 회사에 있는 사람
  • [백준/Python] 2164번 - 카드 2
  • [백준/Python] 2748번 - 피보나치 수 2
  • [백준/Python] 1600번 - 말이 되고픈 원숭이
빵빵0
빵빵0
(아직은) 공부하고 정리하는 블로그입니다.
  • 빵빵0
    Hack Your World
    빵빵0
  • 전체
    오늘
    어제
    • 분류 전체보기 (92)
      • Error Handling (7)
      • Project (5)
        • MEV (2)
      • Architecture (0)
        • API (0)
        • Cache (0)
        • 사소한 고민거리 (0)
      • Computer Science (4)
        • Data Structure (2)
        • Database (1)
        • Cloud (0)
        • OS (0)
        • Infra, Network (1)
        • AI (0)
      • Language (8)
        • Go (8)
        • Rust (0)
        • Python (0)
        • Java (0)
      • Algorithm (40)
        • BaekJoon (18)
        • Programmers (7)
        • LeetCode (6)
        • NeetCode (9)
      • SW Books (9)
        • gRPC Up & Running (1)
        • System Design Interview (2)
        • 스프링 입문을 위한 자바 객체지향의 원리와 이해 (6)
        • 블록체인 해설서 (0)
        • 후니의 쉽게 쓴 CISCO 네트워킹 (0)
      • BlockChain (4)
        • Issues (0)
        • Research (4)
        • Tech (0)
      • Own (8)
        • TIR(Today I Read) (3)
        • Personal (2)
        • Novel (0)
        • Memo (3)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    BFS
    goroutine
    Programmers
    context
    NeetCode
    candlechart
    Greedy
    백준
    ethereum
    BaekJoon
    chart
    blockchain
    LeetCode
    Palindrome
    two pointer
    2024
    golang
    KBW
    프로그래머스
    MEV
    MongoDB
    go
    EVM
    스택
    큐
    BEAKJOON
    Python
    블록체인
    DP
    Hash Table
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.4
빵빵0
[백준/Python] 15988번 - 1, 2, 3 더하기 3
상단으로

티스토리툴바