Enochkon's blog

문제

코드

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. 전부 순회한 후 제일 마지막 최대값을 출력해준다.

문제

코드

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를 전부 돌린 후 경로의 제일 끝 부분중 최소값을 출력한다.

문제

코드

from collections import deque 

def solution(board):
    answer = 0
    board = [list(_) for _ in board]
    row, col = len(board), len(board[0])
    res = [[0 for i in range(len(board[0]))] for j in range(len(board))]
    d = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    q = deque()
    
    def slide(i,j,dr,dc):
        while True:
            ci,cj = i + dr, j + dc
            if not (0 <= ci < row and 0 <= cj < col) or board[ci][cj] == 'D':
                return ci-dr, cj-dc
            i,j=ci,cj
                
    for i in range(row):
        for j in range(col):
            if board[i][j]== 'R':
                q.append((i,j,0))
    while q:
        cx, cy, dist = q.popleft()
        res[cx][cy]=dist
        if(board[cx][cy]=='G'):
            answer=dist
            break
        for dr , dc in d:
            nx,ny=slide(cx,cy,dr,dc)
            if(res[nx][ny]==0):
                res[nx][ny]=1
                q.append((nx,ny,dist+1))
    
    if(answer==0):
        return -1
    else:
        return answer

풀이

• 리코쳇 로봇 최소 경로 찾기

1. 문자열을 리스트화 시켜준다.
2. 시작지점 R 부터 목적지 G 지점까지 도달하는 경로를 찾는다.
   1. BFS를 사용한다.
   2. 한칸씩 이동시키는 것이 아닌 slide 함수를 사용해서 진행방향에 벽 혹은 끝까지 진행하는 좌표를 얻는다.
   3. 해당 좌표를 지나간적이 없으면 q에 추가해준다.
   4. 만약 현재 좌표가 ‘G’면 answer에 거리를 추가한다
3. 모든 탐색이 끝난 후 answer이 0인 경우에는 경로를 못찾은것이기 때문에 -1을 아니면 answer을 출력한다.

문제

코드

from collections import deque 

def solution(maps):
    maps = [list(_) for _ in maps]
    rows, cols = len(maps), len(maps[0])
    distance = [[-1 for _ in range(cols)] for _ in range(rows)]
    d = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    q = deque()
    
    for i in range(rows):
        for j in range(cols):
            if maps[i][j] == 'L':
                q.append((i, j, 0))
                distance[i][j] = 0
    while q:
        cx, cy, dist = q.popleft()
        
        for dx, dy in d:
            nx, ny = cx + dx, cy + dy
            if 0 <= nx < rows and 0 <= ny < cols and maps[nx][ny] != 'X' and distance[nx][ny] == -1:
                distance[nx][ny] = dist + 1
                q.append((nx, ny, dist + 1))
                
    l_dist, e_dist = -1, -1
    for i in range(rows):
        for j in range(cols):
            if maps[i][j] == 'S' and l_dist == -1:
                l_dist = distance[i][j]
            if maps[i][j] == 'E':
                e_dist = distance[i][j]
    
    if l_dist == -1 or e_dist == -1:
        return -1
    else:
        return l_dist + e_dist

풀이

• 시작지점부터 레버까지, 그리고 레버부터 탈출지점까지의 거리를 구해라

1. 입력받은 문자열을 리스트형태로 변환
2. 거리를 입력할 배열 구현
3. 시작지점부터 바로 탈출지점까지 가는게 아닌 중간에 레버를 올려야하므로 레버를 기준으로 시작지점과 탈출지점의 최단거리를 구하면 된다고 생각
   1. bfs를 활용해 레버의 위치인 ‘L’부터 시작, 전체 미로의 거리를 L을 기준으로 기입
   2. 거리를 입력한 distance 배열에서 시작지점인 S와 탈출지점인 E의 좌표에 대한 거리의 합을 출력
   3. 만약 하나라도 -1인 경우 길이 없는것이므로 -1 출력

특이사항

• 출발 지점부터 레버까지와 레버부터 도착 지점까지의 길이 중복되도 된다길래 어떻게 구현해야할지 생각하다가, 두번의 bfs를 돌리면 되겠다고 생각했다. → 하지만 이렇게 구현할 경우 낭비가 심하다고 생각. → 중간 지점인 레버를 기준으로 거리를 구하면 bfs를 한번만 돌릴 수 있다고 생각 후 구현

문제

코드

from collections import deque

def solution(s):
    q = deque()
    for i in range(len(s)):
        if(len(q)==0 or s[i]!=q[len(q)-1]):
            q.append(s[i])
        elif(s[i]==q[len(q)-1]):
            q.pop()
    return 1 if len(q)==0 else 0

풀이

• 문자열에서 연속으로 오는 문자를 제거할 때 전부 제거할 수 있는지를 확인한다.
• 스택의 개념을 사용하면 손쉽게 풀 수 있음

1. 스택 역할을 해주기 위해 deque 선언
2. s문자열을 for문으로 돌면서 문자 제거
   1. q가 비어있거나 q의 마지막 문자와 현재의 문자가 다르면 q에 넣어준다.
   2. 만약 q의 마지막 문자와 현재 문자가 같으면 q를 pop해준다.
3. 마지막에 q가 비어있을 경우 1을 아닐경우 0을 출력한다.