[백준/Python] 1463. 1로 만들기

2024. 12. 26. 17:39·CODING_TEST

※ 문제

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

※ 문제 유형

다이나믹 프로그래밍 (SILVER_3)

※ 나의 풀이

  • DP로 문제 해결
import sys

N = int(sys.stdin.readline())

dp = [0] * (N + 1)
dp[1] = 0

for i in range(2, N + 1):
    # 이전 index의 값 + 1(1을 뺀다는 규칙)으로 저장
    dp[i] = 1 + dp[i - 1]

    # 3으로 나누어 떨어지면 3으로 나누고, dp[i] 중 최솟값으로 저장
    if i % 3 == 0:
        dp[i] = min(dp[i], 1 + dp[i // 3])

    # 2으로 나누어 떨어지면 2으로 나누고, dp[i] 중 최솟값으로 저장
    if i % 2 == 0:
        dp[i] = min(dp[i], 1 + dp[i // 2])

print(dp[N])
  • 12 의 경우를 위해 최솟값을 고려
    • 12 -> 4 -> 2 -> 1
    • 12 -> 6 -> 3 -> 1
    • 12 -> 6 -> 2 -> 1
    • 12 -> 11 -> 10 -> 9 -> 3 -> 1

 

'CODING_TEST' 카테고리의 다른 글

[백준/Python] 14916. 거스름돈  (0) 2024.12.29
[백준/Python] 9095. 1, 2, 3 더하기  (1) 2024.12.26
[백준/Python] 5525. IOIOI  (0) 2024.12.26
[프로그래머스/Python] 피보나치 수  (0) 2024.12.25
[프로그래머스/Python] 교점에 별 만들기  (0) 2024.12.24
'CODING_TEST' 카테고리의 다른 글
  • [백준/Python] 14916. 거스름돈
  • [백준/Python] 9095. 1, 2, 3 더하기
  • [백준/Python] 5525. IOIOI
  • [프로그래머스/Python] 피보나치 수
YAHO_STUDY
YAHO_STUDY
DATA&AI_study.zip
  • YAHO_STUDY
    YAHO_CODE
    YAHO_STUDY
  • 전체
    오늘
    어제
    • 분류 전체보기 (57)
      • Paper Review (0)
      • SQL (16)
      • CODING_TEST (21)
      • Time Series (0)
      • DL (20)
        • NLP (5)
        • LLM&RAG (15)
        • Recommender System (0)
  • 블로그 메뉴

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

  • 공지사항

  • 인기 글

  • 태그

    graph
    RNN
    runpod
    양자화
    한 권으로 끝내는 실전 llm 파인튜닝
    qlora
    Gemma
    Programmers
    pagedattention
    quantization
    fine-tuning
    PEFT
    SQL
    MySQL
    DP
    coding_test
    boj
    prompt-tuning
    hash
    Lora
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
YAHO_STUDY
[백준/Python] 1463. 1로 만들기
상단으로

티스토리툴바