Enochkon's blog

문제

코드

from collections import deque
def bfs(n):
    q = deque([(n, 0)])
    visited = set([n]) 
    while q:
        cur, count = q.popleft()
        if cur == 1:
            return count
        if cur % 3 == 0 and (cur // 3) not in visited:
            q.append((cur // 3, count + 1))
            visited.add(cur // 3)
        if cur % 2 == 0 and (cur // 2) not in visited:
            q.append((cur // 2, count + 1))
            visited.add(cur // 2)
        if (cur - 1) not in visited:
            q.append((cur - 1, count + 1))
            visited.add(cur - 1)
    return -1  
n=int(input())
print(bfs(n))

풀이

1. n을 입력받는다.
2. 입력받은 n을 bfs함수에 넣고 돌려준다. 문제에서 주어진 조건을 만족하면 q에 넣는다.
   • X가 3으로 나누어 떨어지면, 3으로 나눈다.
   • X가 2로 나누어 떨어지면, 2로 나눈다.
   • 1을 뺀다.
3. 단 n의 크기가 최대 10^18로 엄청 크다. 그러므로 최대한 중복된 값을 탐색하지 않기 위해서 visited라는 set()을 선언한다.
4. 매번 얻는 값들을 visited에 넣어주고, bfs 시행 시 조건을 만족해도 visited에 있는 수들은 q에 넣지 않는다.(중복을 피한다)
5. 1이 되면 횟수를 return한다.

문제

코드

import sys
import copy
input = sys.stdin.readline
n= int(input())
# dp배열을 쓰고 싶지만 메모리가 부족하여 현재층과 바로 위층에 사용한 배열만 초기화
bq=[[0,0],[0,0],[0,0]]
cq=[[0,0],[0,0],[0,0]]
for i in range(n):
    arr=list(map(int,input().split()))
    #최대값 구하기
    cq[0][0]=max(bq[0][0],bq[1][0])+arr[0]
    cq[1][0]=max(bq[0][0],bq[1][0],bq[2][0])+arr[1]
    cq[2][0]=max(bq[1][0],bq[2][0])+arr[2]

		#최소값 구하기
    cq[0][1]=min(bq[0][1],bq[1][1])+arr[0]
    cq[1][1]=min(bq[0][1],bq[1][1],bq[2][1])+arr[1]
    cq[2][1]=min(bq[1][1],bq[2][1])+arr[2]
    bq=copy.deepcopy(cq)
resMax=0
resMin=100000000
for i in range(3):
    resMax=max(resMax,max(bq[i]))
    resMin=min(resMin,min(bq[i]))
print(resMax,resMin)

풀이

• 간단한(하지만 조건있는) dp 문제
• 메모리가 굉장히 작으므로, 전체를 저장하는게 아닌 사용하는 부분을 계속 업데이트 하는 방식으로 푼다.

1. 높이 n을 입력받는다.
   • dp 문제이지만 여기서 메모리 크기가 4mb이다. 그러므로 층을 한층씩 내려가면서 본다.
   • 각 층에서 내려갈 수 있는 부분은 인접해 있는 부분이기 때문에 거꾸로 밑층에서도 인접한 곳에서만 올 수 있다.
   • 그러므로 dp[i][0] (왼쪽) : dp[i-1][0] (왼쪽 위), dp[i-1][1] (가운데 위) 중 하나 dp[i][1] (가운데쪽) : dp[i-1][0] (왼쪽 위), dp[i-1][1] (가운데 위), dp[i-1][2] (오른쪽 위) 중 하나 dp[i][2] (오른쪽) : dp[i-1][1] (가운데 위), dp[i-1][2] (오른쪽 위) 중 하나 이다.
   • 최소값과 최대값을 둘다 구하므로, 각각의 위치에 최소,최대를 둘다 구해서 표시해준다.
   • 현재 층(cq)과 바로 위층(bq)만을 사용하고, 다음 층으로 넘어가면 bq=cq로 업데이트 해준다.n만큼 한층씩 내려가면서 최대값과 최솟값을 기록하면서 내려간다.

2. 반복문을 전부 돌고, 1층에서의 최대값과 최소값을 찾아서 출력한다.

특이사항

• dp의 점화식은 대놓고 문제에서 그림으로 주지만, 메모리가 굉장히 제한적이여서 쉽지 않은 문제였다.
• dp배열을 cq와 bq로 바꿨는데도 메모리 초과→ 입력받는 arr도 한줄씩 받게 변경 → 시간초과가 나서 sys로 입력속도 빠르게함 → 성공

문제

코드

T = int(input())
for _ in range(T):
    N = int(input())
    arr = [list(map(int,input().split()))]
    arr.append(list(map(int,input().split())))
    res=[[0 for _ in range(N+1)] for _ in range(2)]
    for i in range(N):
        if(i==0):
            res[0][i+1]=arr[0][i]
            res[1][i+1]=arr[1][i]
            continue
        res[0][i+1]=max(res[1][i]+arr[0][i],res[1][i-1]+arr[0][i])
        res[1][i+1]=max(res[0][i]+arr[1][i],res[0][i-1]+arr[1][i])
    print(max(max(res[0]),max(res[1])))

풀이

1. 시행횟수 T와 스티커사진의 길이 N, 그리고 각 스티커의 점수를 입력 받는다.
2. 입력 받은 스티커 사진을 조건에 맞게 찢어서 최대 점수를 얻는 방법을 구한다. (res배열은 해당 위치 최고 점수의 합)1 2

   1	2
   		3

   1. 우선 첫번째 위치의 경우에는 온전히 res배열에 그 스티커의 점수를 저장한다.
   2. 두번째부터 점화식을 세워서 구해준다.
   3. 위의 표처럼 이런 상황에서 3의 최대값을 구하려면 우선 (2까지의 점수합 + 3의 점수)이 있다. 그리고 또한 스티커를 뗀 부분의 상하좌우를 못쓰게 되므로 만약 1까지의 점수합이 더 크다면 (1까지의 점수합 + 3의 점수) 의 경우가 존재한다. 즉 max((2까지의 점수합 + 3의 점수), (1까지의 점수합 + 3의 점수))을 구하게 된다면 해당 위치의 스티커의 최대점수를 얻을 수 있다.
   4. 끝까지 최대점수를 구한뒤 max()함수를 사용하여 최대값을 구한 후 출력해준다.

문제

코드

N,M = map(int,input().split())
check = [0 for _ in range(N)]
arr = list(map(int,input().split()))
res=set([])
arr.sort()

def solve(cur,count):
    if count==M:
        res.add(tuple(cur))
    for i in range(N):
        if(check[i]!=0):
            continue
        cur.append(arr[i])
        check[i]=1
        solve(cur,count+1)
        check[i]=0
        cur.pop()

solve([],0)
res=list(res)
a=len(res[0])
res.sort(key=lambda x : tuple(x[i] for i in range(a)))
for i in res:
    tmp = tuple(str(j) for j in i)
    print(str(" ").join(tmp)

풀이

1. N,M을 입력받고 N크기의 배열 arr을 입력받는다.
2. check 배열을 만들어주고, arr을 오름차순으로 정렬해준다.
3. solve함수를 호출한다.
   1. solve함수에서 M의 크기를 만들기 위해서 check로 중복된 값을 제외하고 solve를 재귀호출 해준다.
   2. 만약 count==M이면 원하는 크기이므로 res배열에 추가해준다. 단, arr에 중복된 수가 있어서 결과가 중복될 수 있으므로 res는 set자료형을 사용해서 중복을 방지한다. set 자료형은 변경가능한 list를 넣지 못하므로 tuple로 바꿔서 넣어준다.
4. solve함수를 다 수행한 후 결과값을 list로 다시 만들어주고 정렬을 해준다.
   1. 정렬을 해줄 때 M의 개수에 따라 정렬 기준이 달라지므로 lambda를 사용할 때 M의 크기만큼 앞에서부터 차례대로 정렬기준을 잡아준다.
5. 정렬을 완료했으면 출력한다.

문제

코드

a={'A':0,'B':1,'C':2,'D':3,'E':4,'F':5,'G':6,'H':7}
b = {v: k for k, v in a.items()}
d = {'R':(0,1),'L':(0,-1),'B':(-1,0),'T':(1,0),'RT':(1,1),'LT':(1,-1),'RB':(-1,1),'LB':(-1,-1),}

king, stone,n=input().split()
n=int(n)

king_loc = [int(king[1])-1,a[king[0]]]
stone_loc = [int(stone[1])-1,a[stone[0]]]

for _ in range(n):
    move=input()
    i,j = d[move]
    if 0<=king_loc[0]+i<8 and 0<=king_loc[1]+j<8:
        if(king_loc[0]+i==stone_loc[0] and king_loc[1]+j==stone_loc[1]):
            if(0<=stone_loc[0]+i<8 and 0<=stone_loc[1]+j<8):
                stone_loc[0]+=i
                stone_loc[1]+=j
                king_loc[0]+=i
                king_loc[1]+=j
        else:
            king_loc[0]+=i
            king_loc[1]+=j
            
print(b[king_loc[1]]+str(king_loc[0]+1))  
print(b[stone_loc[1]]+str(stone_loc[0]+1))

풀이

• 체스판에서 돌과 킹의 위치를 움직인 후 위치를 출력해라

1. 킹과 돌 그리고 움직이는 횟수 n을 입력 받는다.
2. 입력 받은 좌표값을 정수로 바꿔주고 움직임을 입력받으며 움직인다.
   • 킹의 다음 움직임이 체스판 안에 있고, 그곳이 돌의 위치가 아닐경우
   • 킹의 다음 움직임이 체스판 안에 있고, 그곳이 돌의 위치이고, 돌을 킹과 같은 방향으로 움직였을 때 체스판 안에 있는 경우
   이렇게 두가지만 체크해서 움직인다.
3. 움직이는 경우는
4. 다 움직인 후 정수를 다시 체스판 위치 문자열로 바꾸서 출력한다.

특이사항

• 처음에는 직접 체스판을 구현하려고 했지만, 단순히 좌표만 구하는 거면 굳이 안그래도 되겠다고 생각

문제

코드

from collections import deque

n = int(input())
q = deque()

q.append((n,0))

while len(q)!=0:
    c,count = q.pop()
    if(c<0):
        continue
    if(c==1):
        print(count+1)
        exit(0)
    if(c==0):
        print(count)
        exit(0)
    
    q.append((c-1,count+1))

    if(str(c).count("1")!=0):
        tmp = list(str(c))
        for i in range(len(tmp)):
            if(tmp[i]=='1'):
                q.append((int(str(c)[0:i]+str(c)[i+1:]),count+1))   

풀이

• 0을 만드는 최소 횟수를 구해라

1빼기 능력 두가지
1. 가지고 있는 수에서 1을 뺀다.가지고 있는 수에 있는 1을 하나 지운다.
2. 지우고 난 뒤 좌우의 수들을 순서대로 다시 합쳐 하나의 수로 만든다. 이때 맨 앞의 연속되는 0은 지워진다.

1. n을 입력 받는다
2. 입력 받은 n을 1빼기 능력을 사용한다.
   1. q에 n을 넣어주거 반복문을 돌린다.
   2. 매 시행마다 1빼기 능력 두가지를 사용해서 시행후의 값을 q에 넣어준다.
   3. 계속 반복문을 돌면서 0이하가 되면 없애고, 0이나 1이 되면 반복문을 중지하고 시행횟수를 출력해라

문제

코드

import sys
from collections import deque
input = sys.stdin.readline

n,m=map(int,input().split())
arr = []
check= [[[0,0,0] for _ in range(m)] for _ in range(n)]
d=[(1,0,'b'),(1,-1,'l'),(1,1,'r')]
q=deque()

for i in range(n):
    arr.append(list(map(int,input().split())))

for i in range(n):
    for j in range(m):
        count=0
        if(i==0):
            check[i][j][0]=check[i][j][1]=check[i][j][2]=arr[i][j]
            continue
        if(i==1):
            if j==0:
                check[i][j][0]=float("inf")
                check[i][j][1]=arr[i][j]+arr[i-1][j]
                check[i][j][2]=arr[i][j]+arr[i-1][j+1]
            elif j==m-1:
                check[i][j][2]=float("inf")
                check[i][j][0]=arr[i][j] + arr[i-1][j-1]
                check[i][j][1]=arr[i][j] + arr[i-1][j]
            else:
                check[i][j][2]=arr[i][j] + arr[i-1][j+1]
                check[i][j][0]=arr[i][j] + arr[i-1][j-1]
                check[i][j][1]=arr[i][j] + arr[i-1][j]
            continue
        if j==0:
            check[i][j][0]=float("inf")
            check[i][j][1]=arr[i][j] + check[i-1][j][2]
            check[i][j][2]=arr[i][j] + min(check[i-1][j+1][0],check[i-1][j+1][1])
        elif j==m-1:
            check[i][j][0]=arr[i][j] + min(check[i-1][j-1][1],check[i-1][j-1][2])
            check[i][j][1]=arr[i][j] + check[i-1][j][0]
            check[i][j][2]=float("inf")
        else:
            check[i][j][0]=arr[i][j] + min(check[i-1][j-1][1],check[i-1][j-1][2])
            check[i][j][1]=arr[i][j] + min(check[i-1][j][0],check[i-1][j][2])
            check[i][j][2]=arr[i][j] + min(check[i-1][j+1][0],check[i-1][j+1][1])

res=float("inf")
for i in range(m):
    res=min(min(check[n-1][i]),res)
print(res)

풀이

• 최소 비용의 경로 찾기

1. 각각의 경로에 드는 연료의 양을 입력받고, 누적 연료를 입력할 check 배열을 추가해준다.
   1. check[i][j][l] : i는 열, j는 행 그리고 l은 바로 전 경로가 어디서 왔는지를 나타낸다
   • l에서 0은 왼쪽 위에서 내려온것, 1은 바로 위에서 내려온것, 2는 오른쪽 위에서 내려온것 이다.
2. 첫번째 구역부터 반복문으로 탐색해준다.
   1. 제일 첫번째인 i==0인 곳은 그 구역 연료의 양을 추가해준다
   2. 두번째인 i==1은 바로 위와 현재 경로만 생각해주면 되므로 각각의 값을 추가해준다.
   3. 그 뒤부터는 최소 연료양의 경로를 추가해준다. 단, 같은 방향이 연속되면 안되기 때문에 방향을 생각해서 계산한다.

우선 각각의 방향에서 온 값을 계산한다
1. 왼쪽에서 내려온 경우 (l==0) check[i][j][0]일때는 왼쪽으로 두번 연속으로 내려오면 안되므로 오른쪽, 왼쪽 으로 내려왔거나 아래 왼쪽으로 내려온 경우만 생각해주면 된다.
즉 arr[i][j] + min(check[i-1][j-1][1],check[i-1][j-1][2])
현재의 값 + (check[i-1][j-1][1] 아래로 내려온 후 왼쪽에서 온 경우와, check[i-1][j-1][2] 오른쪽에서 내려온 후 왼쪽에서 내려온 경우 중 작은 값은 넣어준다.)

2. 바로 아래로 내려온 경우 (l==1)
arr[i][j] + arr[i][j] + min(check[i-1][j][0],check[i-1][j][2])
현재의 값 + (check[i-1][j][0] 왼쪽에서 내려온 후 아래로 내려온 경우와, check[i-1][j][2] 오른쪽에서 내려온 후 아래로 내려온 경우 중 작은 값은 넣어준다.)

3. 오른쪽에서 아래로 내려온 경우 (l==2)
arr[i][j] + min(check[i-1][j+1][0],check[i-1][j+1][1])
현재의 값 + (check[i-1][j+1][0] 왼쪽에서 내려온 후 오른쪽으로 내려온 경우와, check[i-1][j+1][1] 바로 아래로 내려온 후 오른쪽에서 내려온 경우 중 작은 값은 넣어준다.)

→ 이 조건을 만족한 후 제일 마지막 행에서 제일 작은 값을 찾아서 출력한다.

특이사항

• 유사문제 17484에서는 bfs로 풀었지만 이번에는 그럴경우 시간초과가 난다. DP로 풀어야 하는문제
• 기본적으로 세 방향에서 내려온 값들을 찾지만, 범위를 벗어나거나 하는 경우에는 inf를 넣어줘서 없는 경로라는 것을 표시한다

문제

코드

from collections import deque

n,m=map(int,input().split())
arr = []
check= [[0 for _ in range(m)] for _ in range(n)]
d=[(1,0,'b'),(1,-1,'l'),(1,1,'r')]
q=deque()

for i in range(n):
    arr.append(list(map(int,input().split())))

for i in range(m):
    q.append((0,i,arr[0][i],'0'))
    while len(q)>0:
        ci,cj,count,direction=q.popleft()
        if check[ci][cj]==0 or check[ci][cj]>count:
            check[ci][cj]=count
        for a,b,c in d:
            if(c==direction):
                continue
            ni=ci+a
            nj=cj+b
            if(0<=ni<n and 0<=nj<m):
                q.append((ni,nj,count+arr[ni][nj],c))
print(min(check[n-1]))

풀이

• 위부터 아래로 내려갈때에 연료를 최소로 사용하는 경로를 찾아라

1. 각 경로의 연로를 입력 받고, 새로운 check 배열을 생성한다.
2. 출발지점들을 q에 넣고, bfs를 돌리며 아래로 나아간다.
   1. 같은방향으로 두번 가지 않게 ‘l’, ‘b’, ‘r’로 구분해서 체크한다.
   2. 만약 현재 위치의 check배열이 0이거나 현재 count보다 크면 count를 넣어준다
3. bfs를 전부 돌린 후 경로의 제일 끝 부분중 최소값을 출력한다.