[Python - Backtracking, Dynamic Programming] 9095 1, 2, 3 더하기

2022. 8. 5. 18:08· Algorithm/Recursion & Backtracking
목차
  1. 👨‍🏫 접근
  2. 👨‍🏫 문제 풀이
  3. 📄 전체 코드 1️⃣
  4. 📄 준비
  5. 📄 풀이
  6. 📄 전체 코드 2️⃣
  7. 📄 준비
  8. 📄 풀이

📌 문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

  • 1+1+1+1
  • 1+1+2
  • 1+2+1
  • 2+1+1
  • 2+2
  • 1+3
  • 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

📌 입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

📌 출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

📌 문제 풀이

👨‍🏫 접근

1, 2, 3을 사용해서 만들 수 있는 경우를 모두 구하는 문제. 다이나믹 프로그래밍과 백트래킹 둘 중 하나를 사용해서 풀이할 수 있다.

 

다이나믹 프로그래밍을 떠올리게 된 방법은, 5는 4에서 1을 더한 것이고 3에서 2를 더한 것이며, 2에서 3을 더한 것으로 볼 수 있기 때문이다. 즉, 이전의 결과를 메모리에 저장해 계속해서 사용하여 풀 수 있었다.

 

백트래킹은 1을 더하는 경우와 2를 더하는 경우, 3을 더하는 경우 총 세 가지 선택지가 계속해서 주어져 탐색하기 때문에 백트래킹을 사용할 수 있었다.

👨‍🏫 문제 풀이

📄 전체 코드 1️⃣

from sys import stdin
input = stdin.readline

T = int(input())


def solve(k):
    global ans
    if k <= 0:
        if k == 0:
            ans += 1
        return

    solve(k - 1)
    solve(k - 2)
    solve(k - 3)


for _ in range(T):
    ans = 0
    solve(int(input()))
    print(ans)

📄 준비

from sys import stdin
input = stdin.readline

T = int(input())
for _ in range(T):
    ans = 0
    solve(int(input()))
    print(ans)

입력이 많으므로 빠르게 입력을 받도록 한다.

 

정답을 입력받을 ans 변수를 두었다.

📄 풀이

def solve(k):
    global ans
    if k <= 0:
        if k == 0:
            ans += 1
        return

    solve(k - 1)
    solve(k - 2)
    solve(k - 3)

재귀를 종료하는 조건은 두 개가 있다.

 

합이 주어진 값과 같은 경우와, 주어진 값보다 커지는 경우이다. 둘 모두 재귀를 마쳐야 하기 때문에 if문을 위와 같이 작성했다.

 

그런 후에, 세 가지 재귀를 들어간다. 1을 더하는 경우, 2를 더하는 경우, 3을 더하는 경우.

📄 전체 코드 2️⃣

import sys
n = int(sys.stdin.readline())

d = [0] * 12
d[1] = 1
d[2] = 2
d[3] = 4
for i in range(4, 12):
    d[i] = d[i - 3] + d[i - 2] + d[i - 1]

for _ in range(n):
    num = int(sys.stdin.readline())
    print(d[num])

📄 준비

import sys
n = int(sys.stdin.readline())

d = [0] * 12
d[1] = 1
d[2] = 2
d[3] = 4

입력이 많으므로 빠르게 입력을 받도록 한다.

 

dp 테이블을 구성하기 전에 값을 먼저 받았다. 왜냐하면, 마이너스 인덱스로 값이 이상하게 저장되는 것을 방지하기 위함이다. 1을 더하는 경우, 2를 더하는 경우, 3을 더하는 경우를 위해서 이전의 경우를 탐색해야 한다. 그런데 기준 값이 2인 상태에서 1, 2, 3을 더한다고 하면, d[i - 3]이 d[-1]로 되어서 정답을 얻을 수 없다.

📄 풀이

for i in range(4, 12):
    d[i] = d[i - 3] + d[i - 2] + d[i - 1]

for _ in range(n):
    num = int(sys.stdin.readline())
    print(d[num])

미리 값을 저장해두고 각 반복에서 값을 출력한다.

📌 총평

의외로 백트래킹으로 3분만에 풀었다. 대박

 

저작자표시 비영리 (새창열림)

'Algorithm > Recursion & Backtracking' 카테고리의 다른 글

[Python - Backtracking] 2661 좋은 수열  (0) 2022.08.11
[Python - Backtracking] 9663 N-Queen  (0) 2022.08.05
[Python - Backtracking] 1182 부분수열의 합  (0) 2022.08.05
[Python - Backtracking] 6603 로또  (0) 2022.08.05
[Python] 1182 부분 수열의 합  (0) 2022.06.22
  1. 👨‍🏫 접근
  2. 👨‍🏫 문제 풀이
  3. 📄 전체 코드 1️⃣
  4. 📄 준비
  5. 📄 풀이
  6. 📄 전체 코드 2️⃣
  7. 📄 준비
  8. 📄 풀이
'Algorithm/Recursion & Backtracking' 카테고리의 다른 글
  • [Python - Backtracking] 2661 좋은 수열
  • [Python - Backtracking] 9663 N-Queen
  • [Python - Backtracking] 1182 부분수열의 합
  • [Python - Backtracking] 6603 로또
턴태
턴태
import { Dream } from "future";
턴태
턴태의 밑바닥부터 시작하는 de-vlog
턴태
전체
오늘
어제
  • ROOT (187)
    • Node.js (37)
      • ES6 (1)
      • TypeScript (3)
      • Express.js (16)
      • NestJS (16)
      • JS (24)
    • 프론트엔드 (29)
      • CS (5)
    • 백엔드 (1)
      • 검색 (2)
      • Database (1)
    • 기타 툴 (1)
      • git (1)
    • 데브옵스 & 인프라 (19)
      • Kubernetes (15)
      • Docker (2)
      • Monitoring (1)
      • IaC (1)
    • Algorithm (90)
      • Implementation & simulation (5)
      • Math (4)
      • Brute Force (1)
      • String (0)
      • Graph (5)
      • Recursion & Backtracking (19)
      • Divide & Conquer (2)
      • Dynamic Programming (18)
      • Greedy (13)
      • Priority Queue (2)
      • Binary Search (6)
      • Data Structure (7)
      • Shortest Path (5)
      • Minimum Spanning Tree (1)
      • Sorting (1)
      • Prefix Sum (1)
    • Linux (1)
      • Ubuntu (1)
    • Diary (5)
      • Algorithm (1)
      • Conference (1)
      • Retrospective (3)
    • Book (0)
      • Self-Development (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • GREEDY
  • 토이프로젝트
  • 함수형 프로그래밍
  • Toy Project
  • baekjoon
  • 타입스크립트
  • 자바스크립트
  • 디프만
  • 파이썬
  • nestjs
  • k8s
  • Kubernetes
  • 백트래킹
  • dynamic programming
  • 다이나믹 프로그래밍
  • TypeScript
  • node.js
  • 인프런
  • 네스트
  • backtracking
  • Omuk
  • 인프런X디프만
  • 백준
  • 노드
  • 익스프레스
  • 쿠버네티스
  • Express
  • N과 M
  • python
  • 오먹

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.1
턴태
[Python - Backtracking, Dynamic Programming] 9095 1, 2, 3 더하기
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.