say repository

import sys
n = int(sys.stdin.readline())
#dp 테이블
d = [0]* (10**6+1)

for i in range(2,n+1):
    #1을 뺸다
    d[i] = d[i-1] + 1
    #3으로 나눠 떨어지면
    if i % 3 == 0:
        d[i] = min(d[i], d[i//3]+1)
    #2으로 나눠 떨어지면
    if i % 2 == 0:
        d[i] = min(d[i], d[i//2]+1)

print(d[n])

풀이

다이나믹 프로그래밍으로 풀었다.

n=10일 때, 직접 그림을 그리면서 풀면 규칙을 찾을 수 있다.

모든 수가 -1은 가능하다.

2와 3으로 나누어 떨어지는 수만 나누어 주면 되는 것이다.

이때, 1을 더하는 것은 횟수를 세어야 하기 때문이다.

반복문을 돌며, 가장 작은 값을 dp 테이블에 넣는다.

i번 째 횟수 = min(i-1, i/3, i/2) +1

int fibonacci(int n) {
    if (n == 0) {
        printf("0");
        return 0;
    } else if (n == 1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}

코드

import sys
t = int(sys.stdin.readline())
for _ in range(t):
    n = int(sys.stdin.readline())
    cnt0 = [1,0]
    cnt1 = [0,1]
    
    if n == 0:
        print(cnt0[0],cnt1[0])
    elif n ==1:
        print(cnt0[1], cnt1[1])
    else:
        for i in range(2,n+1):
            cnt0.append(cnt1[i-1])
            cnt1.append(cnt0[i-1] + cnt1[i-1])
        print(cnt0.pop(), cnt1.pop())

풀이

재귀 함수를 사용하면 시간 초과가 당연히 나고 다이나믹 프로그래밍을 활용해야한다.

Bottom-Up 방법으로 n이 0부터 n까지의 경우의 0과 1이 출현하는 빈도수를 구하자.

점화식을 만들기 위해 규칙을 찾아보면 다음과 같다.

• i번째 0 출현 = i-1 번째 1 출현
• i번째 1 출현 = i-1 번째 0 출현 + i-1 번째 1 출현

n이 0과 1일 때는 리스트에 넣어두고 n이 2일 때부터 반복문을 돌며 점화식을 수행한다.

cnt0과 cnt1 배열의 마지막 원소가 정답이다.

import sys
from collections import deque
n, k = map(int,sys.stdin.readline().split())
MAX = 100000
visited = [0] * (MAX+1)

def bfs():
    q = deque()
    q.append(n)
    while q:
        x = q.popleft()
        if x == k:
            print(visited[x])
            break
        for nx in (x-1, x+1, x*2):
            if 0<=nx<=MAX and not visited[nx]:
                visited[nx] = visited[x] + 1
                q.append(nx)
bfs()

풀이

수빈과 동생이 움직일 수 있는 조건이 0부터 100000 니까 max값을 준다.

그리고 bfs을 실행해서 처음 수빈이의 위치를 큐에 넣는다.

수빈이가 동생을 찾을 때까지

수빈이가 움직일 수 있는 경우인 걷기 x-1 와 x+1 , 순간이동 x*2 이 세 가지씩 그래프를 뻗어나간다.

그래프가 한 층씩 생길때마다 전 층의 값 +1을 해주고 동생을 찾으면 이 값을 리턴한다.

import sys
n = int(sys.stdin.readline())
chess = [0] * n
cnt = 0

def possible(x):
    for i in range(x):
        #행 돌면서
        #상하좌우 or 대각선에 퀸이 있다면 False 반환
        #여기서 대각선은 행-행 = 열-열
        if chess[i] == chess[x] or abs(chess[x]-chess[i]) == abs(x-i):
            return False
    return True

def solution(x):
    global cnt
    #재귀로 x가 계속 +1 되는데 x가 n이 되면 경우의 수 +1
    if x==n:
        cnt+=1
    else:
        for i in range(n):
            #chess판의 (x,i)에 퀸을 놓는다.
            chess[x] = i
            if possible(x):
                #퀸이 상하좌우, 대각선으로 공격할 수 없다면 다음 퀸 놓기
                solution(x+1)

solution(0)
print(cnt)

풀이

재귀함수 dfs와 백트래킹을 활용해 풀었다.

1) 퀸을 체스판에 놓는다.

chess[i] = j 는 ( i, j ) 에 퀸이 있다는 뜻이다.

2) 놓은 퀸의 상하좌우에 퀸이 있으면 False

3) 놓은 퀸의 대각선에 퀸이 있으면 False

4) 퀸의 개수가 입력값일 때 cnt+=1

python으로는 계속 시간초과가 난다.

pypy3로 통과했다.

python으로 시간초과가 나지 않는 방법이 있으면 알려주세요...

코드 1

import sys
t = int(sys.stdin.readline())
#스택
for i in range(t):
    string = sys.stdin.readline().rstrip()
    string += " "

    stack = []
    for j in string:
        if j != " ":
            stack.append(j)
        else:
            while stack:
                print(stack.pop(),end = "")
            print(' ',end="")

풀이 1

문자열을 넣고 거꾸로 출력을 하니까 스택 자료구조로 구현했다.

문자열을 스택에 넣고 " "을 만나면 pop() 한다.

주의할 점은 마지막 문자열 끝에 " "가 안 들어가니까 뒤집기가 안된다. 

그래서 마지막 문자열에도 " "을 넣어준다.

코드 2

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

#문자열 슬라이싱
for i in range(t):
    string = sys.stdin.readline().rstrip().split()
    for str in string:
        print(str[::-1],end=" ")
    print()

풀이 2

python은 문자열을 다루기 좋은 언어이다.

python의 장점을 활용해 " "마다 잘라서 str[::-1] 을 사용해 뒤집어줬다.

import sys
t = int(sys.stdin.readline())
def sol(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    elif n == 3:
        return 4
    else:
        return sol(n-3) + sol(n-2) + sol(n-1)

for i in range(t):
    n = int(sys.stdin.readline())
    print(sol(n))

풀이

n이

1 일 때 1 -> 총 1가지

2일 때 1+1, 2 -> 총 2가지

3일 때 1+1+1, 1+2, 2+1, 3 -> 총 4가지

4일 때 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 1+3, 3+1, 2+2 -> 총 7가지

5일 때 1+1+1+1+1, 1+1+1+2, 1+1+2+1, 1+2+1+1, 2+1+1+1, 1+1+3, 1+3+1, 3+1+1, 2+3, 3+2, 2+2+1, 2+1+2, 1+2+2 -> 총 13가지

...

이렇게 구해보면 규칙을 찾을 수 있다.

점화식을 세워 구하면 된다.

f(n) = f(n-3) + f(n-2) + f(n-1) (단, n>3)

import sys
n, s = map(int,sys.stdin.readline().split())
arr = list(map(int,sys.stdin.readline().split()))

def dfs(idx,sum):
    global cnt
    if idx>=n:
        return
    sum += arr[idx]
    if sum == s:
        cnt+=1
    dfs(idx+1, sum)
    dfs(idx+1, sum-arr[idx])

cnt = 0
dfs(0,0)
print(cnt)

풀이 1

백트래킹으로 구현했다. 

완전탐색을 하면서 불필요한 탐색은 가지치기하는 방법이다.

dfs을 하면서

1. 현재 arr [idx] 을 포함하는 경우

2. 현재 arr [idx] 을 포함하지 않는 경우

경우의 수를 가지치기 한다.

코드 2

import sys
from itertools import combinations
n, s = map(int,sys.stdin.readline().split())
arr = list(map(int,sys.stdin.readline().split()))

#조합
cnt = 0
for i in range(1,n+1):
    comb = list(combinations(arr,i))
    for j in comb:
        if sum(j) == s:
            cnt+=1

print(cnt)

풀이 2

조합을 사용해서 크기가 1부터 n까지의 부분수열을 만들고 그 합이 s일 때 cnt+=1 한다.