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. 정렬을 완료했으면 출력한다.

문제

코드

def solution(tickets):
    tickets.sort(reverse=True)
    routes = {}
    
    for start,end in tickets:
        if start in routes:
            routes[start].append(end)
        else:
            routes[start] = [end]
    stack = ["ICN"]
    path = []
    
    while stack:
        top = stack[-1]
        if top in routes and routes[top]:
            stack.append(routes[top].pop())  
        else:
            path.append(stack.pop())  
    
    return path[::-1]  
    

풀이

• 주어진 비행기표를 다 사용한 후 여행경로를 출력해라

1. 알파벳 순서가 빠른것을 먼저 출력하라고 했기 때문에 tickets을 역순으로 정렬
2. 우선 routes라는 딕셔너리를 만들어 출발지는 key로 목적지는 value로 만들어준다.
3. stack 으로 사용할 배열에 제일 첫번째에 “ICN”을 넣어주고, while문을 돌린다.
4. while문을 돌리면서 갈 경로가 있으면 스택에 추가해주고, 아니면 stack에서 꺼내 path에 추가한다
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이 되면 반복문을 중지하고 시행횟수를 출력해라

문제

1535번: 안녕

코드

n = int(input())
lost = list(map(int,input().split()))
happy = list(map(int,input().split()))
hp = 100
pleasure = 0
arr= [[0 for _ in range(101)] for _ in range(n+1)]

for i in range(1,n+1):
    for j in range(1,101):
        if(j-lost[i-1]>0):
            arr[i][j] = max(arr[i-1][j], arr[i-1][j-lost[i-1]] + happy[i-1])
        else:
            arr[i][j]=arr[i-1][j]

print(arr[n][100])

풀이

• 간단한 dp 문제

1. 사용 체력과 얻는 기쁨을 배열로 받아준다.
2. dp 배열을 arr[i][j] (i : 체력, j : 사람 순서)로 작성해준다.
3. 이중 반복문을 사용해서 체력이 0 이하가 되면 바로 인사를 하지 않고 바로 전 사람까지의 기쁨 값을 가져온다 (i-1)
   1. 체력이 0이하로 떨어지지 않으면 바로전까지의 기쁨 값과, 인사를 했을 때 추가되는 값중 큰 값을 새로 입력해준다.
4. 전부 순회한 후 제일 마지막 최대값을 출력해준다.