say repository

문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

import sys
n = int(sys.stdin.readline())
d = [0]*1001
d[1]=1
d[2]=2
for i in range(3,n+1):
    d[i] = d[i-1]+d[i-2]
print(d[n] % 10007)

풀이

다이나믹 프로그래밍이다.

d[1] = 1

d[2] = 2

d[3] = 3 

d[4] = 5

d[5] = 8

...

규칙이 보인다.

import sys
import math
n = int(sys.stdin.readline())
arr = [False]+[True]*(n)
prime_num = []
for i in range(2,int(math.sqrt(n))+1):
    if arr[i]:
        for j in range(i*2,n+1,i):
            arr[j]=False
for i in range(2,n+1):
    if arr[i]:
        prime_num.append(i)

result = 0
start = 0
end = 0

while end<=len(prime_num):
    tmp = sum(prime_num[start:end])
    if tmp == n:
        result+=1
        end+=1
    elif tmp<n:
        end+=1
    else:
        start+=1
print(result)

풀이

1) 에라토스테네스의 체 알고리즘

한정된 범위 안 소수 구하기

2) 투포인터

start, end 변수로 end가 끝이 될때까지, 현재가 원하는 값보다 작으면 end+=1, 아니면 start+=1

문제

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.

<그림 1>

예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.

<그림 2>

계단 오르는 데는 다음과 같은 규칙이 있다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

import sys
n = int(sys.stdin.readline())
d = [0] * 301
s = [0] * 301
for i in range(n):
    s[i] = int(sys.stdin.readline())
    d[0] = s[0]
    d[1] = s[0] + s[1]
    d[2] = max(s[1]+s[2], s[0]+s[2])
    for i in range(3,n):
        d[i] = max(d[i-3]+s[i-1]+s[i], d[i-2]+s[i])
print(d[n-1])

풀이

다이나믹 프로그래밍 문제이다.

n이 6일 때를 그림을 그리면서 점화식을 찾아보자.

dp 테이블 d를 만들고 계단의 0번째 값을 넣는다.

1로 가는 길은 0번째 1번째 계단 값을 넣는다.

d[0] = s[0]
d[1] = s[0] + s[1]

2로 가는 길은 0에서 2 or 1에서 2 이다. 

그 중 더 큰 값을 선택한다.

d[2] = max(s[1]+s[2], s[0]+s[2])

그 다음엔 for문을 돌아야하고 마지막 계단은 꼭 밟아야한다.

생각할 것은 마지막 계단 바로 전 계단을 밟을지 or 전전 계단을 밟을지이기 때문에 점화식이 이렇게 된다.

d[i] = max(d[i-3]+s[i-1]+s[i], d[i-2]+s[i])

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으로 시간초과가 나지 않는 방법이 있으면 알려주세요...