백준 3주차

13일차(1/20)

 

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

from collections import deque


def bfs(a, b):
    # 큐에 (현재 값, 연산 횟수)로 시작 상태를 넣음
    queue = deque([(a, 1)])  # 시작 값 a에서 연산 1번부터 시작
    visited = set([a])  # 방문한 값들을 기록하여 중복 방지

    while queue:
        current, count = queue.popleft()

        # 2를 곱한 값이 B와 같으면 바로 반환
        if current == b:
            return count

        # 두 가지 연산을 시도
        # 1. 2를 곱한다.
        next_value = current * 2
        if next_value <= b and next_value not in visited:
            visited.add(next_value)
            queue.append((next_value, count + 1))

        # 2. 1을 수의 오른쪽에 추가한다.
        next_value = current * 10 + 1
        if next_value <= b and next_value not in visited:
            visited.add(next_value)
            queue.append((next_value, count + 1))

    return -1  # 불가능한 경우


a, b = map(int, input().split())

result = bfs(a, b)
print(result)

 

14일차(1/21)

 

DP는 정신만 차리면 된다.

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

 

t=int(input())
for _ in range(t):

    n=int(input())
    arr=[]

    for _ in range(2):
        arr.append(list(map(int,input().split())))
    dp=[[0]* n for _ in range(2)]

    for i in range(n):
        for j in range(2):
            if i == 0:
                dp[j][i] = arr[j][i]
            elif i == 1:
                dp[j][i] = arr[j][i] + dp[1 - j][i - 1]
            else:
                if j==0:
                    dp[j][i]=arr[j][i]+max(dp[j+1][i-1],dp[j+1][i-2],dp[j][i-2])
                else:
                    dp[j][i]=arr[j][i]+max(dp[j-1][i-1],dp[j-1][i-2],dp[j-1][i-2])
    print(max(max(dp[0]),max(dp[1])))

 

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

t=int(input())
for _ in range(t):
    n=int(input())
    dp=[0]*(n+1)

    for i in range(n):
        if i==0 or i==1 or i==2:
            dp[i]=1
        else:
            dp[i] = dp[i-2]+dp[i-3]
    print(dp[-2])

 

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

n=int(input())
arr=[]
dp=[]
for _ in range(n):
    arr.append(list(map(int, input().split())))
dp=[[0]* n for _ in range(n)]
dp[0][0] = 1  

for i in range(n):
    for j in range(n):
        k=arr[i][j]
        if k==0:
            continue
        if i+k<n:
            dp[i + k][j] += dp[i][j]
        if j+k<n:
            dp[i][j+k] += dp[i][j]
print(dp[-1][-1])

 

15일차(1/22)

 

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

 

전형적인 LIS문제

이때, max(dp) != dp[-1] 임을 주의해야 한다.

'''
8
1 6 2 5 7 3 5 6
dp=[1,1,1,1,1,1,1,1]
arr=[1,6,2,5,7,3,5,6]

i=1일때, j=0
dp=[1,2,1,1,1,1,1,1]

i=2일때, j=0,1
dp=[1,2,2,1,1,1,1,1]
dp=[1,2,2,1,1,1,1,1]

'''
n=int(input())
dp=[1]*n
arr =list(map(int,input().split()))
for i in range(1,n): #자기자신
    for j in range(i):
        if arr[j]<arr[i]: #뒷 숫자가 더 크면
            if dp[i]<dp[j]+1:
                dp[i]=dp[j]+1
print(max(dp))

 

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

확실히 실버 dp문제는 문제가 참 dp 스러운 것 같다.

'''
n=0일때 1가지 = 1
n=1일때 1+2가지 =3
N=2일때 1+4+2가지 = 7
n=3일때 1+6+8+2가지 = 17
n=4일때 1+8+18+12+2가지 = 41
1*2+1
3*2+1
7*2+3
17*2+7
41*2+17
즉, 점화식이 dp[n]=dp[n-1]*2+dp[n-2]가 나온다.
'''

n=int(input())
dp=[0]*(n+1)
for i in range(n+1):
    if i==0:
        dp[i]=1
    elif i==1:
        dp[i]=3
    else:
        dp[i]=2*dp[i-1]+dp[i-2]
print(dp[n]%9901)

100,000이기에 메모리 초과

나머지 연산을 각 배열마다 해줘야, 메모리 초과를 방지 할 수 있다.

n=int(input())
dp=[0]*(n+1)
for i in range(n+1):
    if i==0:
        dp[i]=1
    elif i==1:
        dp[i]=3
    else:
        dp[i]=(2*dp[i-1]+dp[i-2])%9901
print(dp[n])

나는 숫자보고 유추에서 풀었는데, 자세한 점화식은 아래 블로그에 잘 나와있다.

https://great-park.tistory.com/131 

 

16일차(1/23)

 

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

국어가 너무 어려워요...

n=int(input())
arr=list(map(int,input().split()))

trues = [0]*51

#해당 말이 나온 횟수 셈
for i in arr:
    trues[i]+=1

#'횟수'와 '숫자'가 같다면, 맞는말
# 가장 큰값이므로 반대에서 돌면서 제일 먼저 오는 0이 아닌값이 될것
for i in range(50,-1,-1):
    if trues[i]==i:
        print(i)
        break
else:
    print(-1)

 

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

메모리 초과

n= int(input())
arr=[]
for _ in range(n):
    arr.append(list(map(int,input().split())))

max_dp = [[0] * 3 for _ in range(n)]

# 첫 행
max_dp[0][0] = arr[0][0]
max_dp[0][1] = arr[0][1]
max_dp[0][2] = arr[0][2]

# 두 번째 행부터 계산
for i in range(1, n):
    max_dp[i][0] = arr[i][0] + max(max_dp[i-1][0], max_dp[i-1][1])
    max_dp[i][1] = arr[i][1] + max(max_dp[i-1][0], max_dp[i-1][1], max_dp[i-1][2])
    max_dp[i][2] = arr[i][2] + max(max_dp[i-1][1], max_dp[i-1][2])

min_dp = [[0] * 3 for _ in range(n)]

# 첫 행
min_dp[0][0] = arr[0][0]
min_dp[0][1] = arr[0][1]
min_dp[0][2] = arr[0][2]

# 두 번째 행부터 계산
for i in range(1, n):
    min_dp[i][0] = arr[i][0] + min(min_dp[i-1][0], min_dp[i-1][1])
    min_dp[i][1] = arr[i][1] + min(min_dp[i-1][0], min_dp[i-1][1], min_dp[i-1][2])
    min_dp[i][2] = arr[i][2] + min(min_dp[i-1][1], min_dp[i-1][2])
print(max(max_dp[n-1]), min(min_dp[n-1]))

 

1/17