Kim Jisong

I am an amazing person.

백준시리즈: 1, 2, 3 더하기

Introduction

재귀 함수를 연습하기 좋은 문제

dp, 백트래킹

https://www.acmicpc.net/workbook/view/6509

1, 2, 3 더하기

dp 문제

import sys
input = sys.stdin.readline

# 1, 1
# 2, 11, 2
# 3, 111, 12, 21, 3
# 4, 1111, 112, 121, 211, 22, 13, 31

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

def find123(dp,num):
    if dp[num] != 0:
        return dp[num]
    else:
        dp[num] = find123(dp,num-1) + find123(dp,num-2) + find123(dp,num-3)
        return dp[num]

T = int(input())
for _ in range(T):
    num = int(input())
    print(find123(dp,num))

1, 2, 3 더하기 2

백트래킹 문제

import sys
input = sys.stdin.readline

n, k = map(int,input().split())
num = []
find_flag = False
cnt = 1
def dfs():
    global cnt
    global find_flag
    if find_flag == True:
        return
    if sum(num) == n:
        if cnt == k:
            print("+".join(map(str,num)))
            find_flag = True
        cnt += 1
        return
    for i in [1,2,3]:
        if i + sum(num) <= n:
            num.append(i)
            dfs()
            num.pop()

dfs()
if find_flag == False:
    print(-1)

1, 2, 3 더하기 3

dp 문제

  • 모듈러 연산은 나눗셈 연산을 제외한 모든 연산에서 분배법칙이 성립한다
    • (A+B)%M = (A%M+B%M)%M
    • (A-B)%M = (A%M-B%M)%M
    • (AB)%M = (A%MB%M)%M
  • 시간 초과 문제로, 바텀업 방식으로 작성해야 함
import sys
input = sys.stdin.readline

T = int(input())

dp = [0]*1000001
dp[1] = 1
dp[2] = 2
dp[3] = 4

cnt = 4
def dynamic(dp,num):
    global cnt
    if dp[num] != 0:
        return dp[num]
    else:
        for n in range(cnt,num+1):
            dp[n] = (dp[n-1] + dp[n-2] + dp[n-3])%1000000009
        cnt = num
        return dp[num]

for _ in range(T):
    in_num = int(input())
    print(dynamic(dp,in_num))

1, 2, 3 더하기 4

1, 2, 3 더하기 5

1, 2, 3 더하기 6

1, 2, 3 더하기 7

1, 2, 3 더하기 8

1, 2, 3 더하기 9

2022

Stack

less than 1 minute read

Introduction

Stack

less than 1 minute read

Introduction

Download-only-one-directory

less than 1 minute read

Git 명령어를 사용한 하위 디렉토리 다운로드 Clone 할 로컬 저장소 생성

Sort

3 minute read

Introduction

Tree

less than 1 minute read

Introduction

Mutex library on C++

less than 1 minute read

#include <iostream> #include <thread> #include <chrono> #include <mutex> #include <atomic> #include <string.h>

TODO

less than 1 minute read

how to costom github blog using jekyll

Welcome to Jekyll!

less than 1 minute read

You’ll find this post in your _posts directory. Go ahead and edit it and re-build the site to see your changes. You can rebuild the site in many different wa...

Back to top ↑