# 9251 LCS
def LCS(SA,SB,SALEN,SBLEN):
global LCS_list
for i in range(1,SALEN+1):
for j in range(1,SBLEN+1):
if SA[i-1] == SB[j-1]:
LCS_list[i][j] = LCS_list[i-1][j-1]+1
else:
LCS_list[i][j] = max(LCS_list[i-1][j],LCS_list[i][j-1])
A = list(input())
B = list(input())
lenA = len(A)
lenB = len(B)
LCS_list = [[0]*(lenB+1) for _ in range(lenA+1)]
LCS(A,B,lenA,lenB)
print(LCS_list[lenA][lenB])
# 14499 주사위 굴리기
# N*M 지도
# 주사위는 윗면이 1 동쪽방향이 3인 상태로 놓아진다.
def roll(direction,nx,ny):
global dice,map_list
if direction == 1:
dice[0],dice[2],dice[3],dice[5] = dice[3],dice[0],dice[5],dice[2]
elif direction == 2:
dice[0],dice[2],dice[3],dice[5] = dice[2],dice[5],dice[0],dice[3]
elif direction == 3:
dice[0],dice[1],dice[4],dice[5] = dice[4],dice[0],dice[5],dice[1]
else:
dice[0],dice[1],dice[4],dice[5] = dice[1],dice[5],dice[0],dice[4]
if map_list[nx][ny]:
dice[5] = map_list[nx][ny]
map_list[nx][ny] = 0
else:
map_list[nx][ny] = dice[5]
N,M,X,Y,K = map(int,input().split())
map_list = [list(map(int,input().split())) for _ in range(N)]
# [1,2,3,4,5,6]
# 동쪽 1 [4,2,1,6,5,3]
# 서쪽 2 [3,2,6,1,5,4]
# 북쪽 3 [5,1,3,4,6,2]
# 남쪽 4 [2,6,3,4,1,5]
dice = [0]*6
dire = [(0,1),(0,-1),(-1,0),(1,0)]
command_list = list(map(int,input().split()))
for command in command_list:
nx = X + dire[command-1][0]
ny = Y + dire[command-1][1]
if 0<=nx<N and 0<=ny<M:
roll(command,nx,ny)
else:
continue
X,Y = nx,ny
print(dice[0])
첫 풀이방식은 문제에 주어진 조건을 그대로 따라 했다.
문제에서 보여준 전개도 대로 실행했다. 일단 크기가 6인 리스트를 만들어 주사위로 지정을 했다.
문제에서 보여준 전개도에서 각 위치에 해당하는 값은 전개도에 있는 값의 -1에 인덱스에 저장을 했다.
즉 정 가운데는 0번 인덱스, 3번 위치에 있는것은 2번 인덱스에 저장을 했다.
이런식으로 주사위를 가정하고, 주사위를 동서남북으로 돌렸을때, 인덱스가 바뀌는 위치를 계산해줬다. 그리고 동서남북에 따라, 주사위가 바뀌는 것을 구현해주었다.
동서남북명령어가 1,2,3,4로 들어오니 그에 맞춰 이동값을 dire에 저장해줬다. 그 다음에는 명령어를 실행시켜주는 반복문을 하고, 범위를 벗어나는 경우에는 아무것도 출력을 하면 안되니 범위를 벗어나는 경우에는 continue로 넘어가준다. 그렇지 않을 때에는, roll이라는 함수를 실행시켜 주사위를 굴리고, 그 위치에 존재하는 값에 따라 문제에 주여진 조건대로 실행시켰다.
하지만 이렇게 풀고난뒤 한가지 불만점이 있었는데, 각 케이스마다 전부 하나하나 인덱스를 바꿔주는 로직이 마음에 들지 않았다.
그래서 개선한 코드는 다음과 같다.
# 14499 주사위 굴리기
# N*M 지도
# 주사위는 윗면이 1 동쪽방향이 3인 상태로 놓아진다.
def roll(direction,nx,ny):
global dice,map_list,moving_dice
dice[0],dice[-1],dice[moving_dice[direction][0]],dice[moving_dice[direction][1]] = dice[moving_dice[direction][0]],dice[moving_dice[direction][1]],dice[-1],dice[0]
if map_list[nx][ny]:
dice[5] = map_list[nx][ny]
map_list[nx][ny] = 0
else:
map_list[nx][ny] = dice[5]
N,M,X,Y,K = map(int,input().split())
map_list = [list(map(int,input().split())) for _ in range(N)]
# [1,2,3,4,5,6]
# 동쪽 1 [4,2,1,6,5,3]
# Top,Bottom,바뀔것1,바뀔것2 = 바뀔것1,바꿀것2,bottm,top
# 서쪽 2 [3,2,6,1,5,4]
# 북쪽 3 [5,1,3,4,6,2]
# 남쪽 4 [2,6,3,4,1,5]
dice = [0]*6
dire = [(0,1),(0,-1),(-1,0),(1,0)]
moving_dice = {1 : [3,2],2:[2,3],3:[4,1],4:[1,4]}
command_list = list(map(int,input().split()))
for command in command_list:
nx = X + dire[command-1][0]
ny = Y + dire[command-1][1]
if 0<=nx<N and 0<=ny<M:
roll(command,nx,ny)
else:
continue
X,Y = nx,ny
print(dice[0])
나머지 로직은 전부 동일하지만, 주사위가 굴러갈때의 규칙성이 있다.
규칙은 다음과 같다.
주사위는 총 6면이 있고, 서로 마주보는걸로 묶을시 3쌍으로 볼수 있다. 주사위를 굴릴 시, 우리가 굴리기전의 Top,bottom 한 쌍과 주사위를 굴러오서 오는 한쌍이 위치가 바뀌고 나머지 한쌍은 그대로 위치한다.
Prev -- >> Next
굴렸을때 Top에 가는 거 Top
굴렸을때 Bottom에 가는 거 Bottom
Top Prev에서 굴렸을때 Bottom에 가는것이 있었던 위치
Bottom Prev에서 굴렸을때 Top에 가는 것이 있었던 위치
글로 설명하기 좀 힘든데 이러한 특징점을 가지고 있따. 그러므로 각 명령어마다, 바뀌는 Index값을 Dictionary에 저장해놓고, 위의 걸 구현해주었다.
같은 코드를 여러번 반복하는 것을 막을 수 있었다. 당연히 실전에서는 위의 풀이방식대로 풀 것 같다.
def nqueen(x):
global cnt
for i in range(x+1):
if x != i:
if (visited[i] == visited[x]) or (abs(visited[i]-visited[x]) == abs(i-x)):
return
if x == N-1:
cnt += 1
return
for i in range(N):
visited[x+1] = i
nqueen(x+1)
N = int(input())
cnt = 0
visited = [-1] * N
for i in range(N):
visited[0] = i
nqueen(0)
print(cnt)
백트래킹을 이용한 유명한 문제 중 하나이다.
적절하게 백트래킹을 하지 않고, 전체탐색을 할시 순열이라, 시간초과가 날 수 밖에 없다.
이 문제는 N과 같은 크기의 visited 1차원 리스트를 만들어줬다.
각 인덱스는 행을 나타내고, 그 안의 값은 열을 나타낸다고 가정을 하자.
그래서 첫번째 행에 0~N-1까지 넣어주고 그 뒤에 nqueen이라는 함수를 실행시켰다.
이 안에서도, 각 인덱스를 넣어주면서 재귀를 진행하는데, 만약에 값이 같은게 있거나, 인덱스의 차와 값의 차이가 동일하시 이것은 대각성분에 존재하는것이므로 종료를 해준다.
위 조건에 걸리지 않고 N-1까지 오면, 모든 곳을 탐색한 것이므로 함수를 종료해주면서 cnt를 1 늘려주면 된다.
# 2714 로봇 시뮬레이션
# A,B, A은 가로, B는 세로 N은 로봇들
# L,R,F : 로봇기준 왼쪽 90도, 로봇방향 기준 오른쪽 90도, 로봇 기준 앞으로 GO
# 잘못된 명령 : Robot X crashes into the wall: X번 로봇이 벽에 충돌
# Robot X crashes into robot Y : X번 로봇이 Y번 로봇에 부딪힘
def rotate_dire(rotate,current):
dire_left = [3,0,1,2]
dire_right = [1,2,3,0]
if rotate == 'L':
return dire_left[current]
else:
return dire_right[current]
def display_crash(flag,*numbers):
if flag:
return f'Robot {numbers[0]} crashes into the wall'
else:
return f'Robot {numbers[0]} crashes into robot {numbers[1]}'
A,B = map(int,input().split())
N,M = map(int,input().split())
robots = {}
robot_place = {}
# E : 0 , S : 1 , W : 2 , N : 3
dire_match = {'E':0,'S':1,'W':2,'N':3}
for robot_number in range(1,N+1):
X,Y,dire = input().split()
robots[robot_number]= (int(X),int(Y),dire_match[dire])
robot_place[(int(X),int(Y))] = robot_number
command_list = []
for _ in range(M):
robot_number,command,repeat = input().split()
command_list.append((int(robot_number),command,int(repeat)))
flag = True
result = 'OK'
go_robots = [(1,0),(0,-1),(-1,0),(0,1)]
while command_list:
command_robot,command,repeat = command_list.pop(0)
cu_X, cu_Y,cu_dire = robots[command_robot]
del robot_place[(cu_X,cu_Y)]
for _ in range(repeat):
if command == 'F':
next_X = cu_X + go_robots[cu_dire][0]
next_Y = cu_Y + go_robots[cu_dire][1]
if 1<= next_X <= A and 1<= next_Y <= B:
if robot_place.get((next_X,next_Y)):
flag = False
result = display_crash(False,command_robot,robot_place[(next_X,next_Y)])
break
else:
cu_X = next_X
cu_Y = next_Y
else:
flag = False
result = display_crash(True,command_robot)
break
else:
cu_dire = rotate_dire(command,cu_dire)
robots[command_robot] = (cu_X,cu_Y,cu_dire)
robot_place[(cu_X,cu_Y)] = command_robot
if not flag:
break
print(result)
이 문제는 구현,시뮬레이션 문제이고 문제에 주어진 조건대로, 진행시키면 되는 문제이다.
여기서 자주 쓰이는 것들은 함수화, 딕셔너리화 해서 편하게 할 수 있도록 진행했다.
먼저 방향을 숫자로 매핑시켜줬다. 그래야 방향전환시 쉽게 찾을수 있기 때문이다.
그래서 나는 E : 0 , S : 1 , W : 2 , N : 3 으로 각각 매핑시켜두었다.
이렇게 하고 방향 전환은 rotate_dire라는 함수를 만들어, 오른쪽 왼쪽일때 각각의 리스트를 만들어주고, 방향의 숫자에 맞춰 방향변경시 변경되는 방향을 넣어두었다.
그 다음으로는 이 문제는 2차원 리스트를 통해 구현하는게 일반적인데, 저 같은 경우엔 해당 2차원 리스트에 저장되어있는 정보들이 극히 일부분이고, 무엇보다, 문제에 주어진 행렬은 우리가 일반적으로 만드는 리스트와 상하반전이기때문에, 딕셔너리를 통해 robot들의 정보와 위치정보를 저장시켜주었다.
리스트를 이용해 풀 사람들은 이동방향시 이동하는 위치를 S,N이 바뀌는것만 주의하면 됩니다.
먼저 robots라는 딕셔너리에는 각각의 로봇넘버를 키로 두고 그 안에는 위치정보와 방향정보를 넣어주었다.
그리고 robot_place라는 딕셔너리에는 로봇들의 위치정보를 키로 두고 그 안에 로봇의 넘버를 넣어주었다.
그 다음에는 동서남북을 go_robots 이라는 변수에 저장시켜줬으며, 우리가 위에 매핑시켜놓은 숫자에 맞춰서, 이동을 다음과 같이 [(1,0),(0,-1),(-1,0),(0,1)] 구현해놨다.
이렇게 사전작업을 해둔뒤, 우리가 저장해놓은 command들을 순차적으로 진행시키면 되는 문제이다.
먼저 cu_X,cu_Y,cu_dire 현재의 로봇의 정보를 가져온다. 그리고 난뒤 robot_place에서 해당 위치의 정보를 삭제해준다. 왜냐하면 이동시 robot_place을 기준으로 이동을 탐색하기 때문에, 삭제를 해주는것이다.
그리고 난뒤 명령어가 F일때에는 로봇의 방향으로 전진하는 것이기 때문에, 우리가 만들어놓은 go_robots을 통해 이동시켜주고, 범위가 넘어가지 않는지, 그리고 robot_place에 이미 이동할려는 위치에 로봇이 존재하는지 판단해준다.
그리고 그 결과에 따라, 아무 이상없이 진행되면 cu_X,cu_Y를 next_X,next_Y로 변경시켜준다.
만약 충돌이 발생시에는 발생경우에 따라 다르게 출력될수 있도록 만든 display_crash를 통해 해주는데, 상황에 따라 함수의 input값이 2개가 될수 있으므로, 가변인자를 통해 구현해주었습니다.
명령어가 'L','R'일때에는 rotate_dire라는 함수를 실행시켜 방향을 변경시켜줍니다.
명령어를 수행 하고 난뒤에는 robots와 robot_place 딕셔너리에 마지막으로 변경된 값들을 저장해주면 됩니다.
모든 명령어를 수행하고 아무 에러가 없을때에는 result의 기본값인 OK가 출력되도록 하고, 아닐시에는 에러 메시지가 출력되도록 구현했습니다.
# 12851 숨바꼭질
N,M = map(int,input().split())
dp = [-1]*100001
if M != N:
stack = [(N,0,'')]
flag = False
result = float('inf')
dire = ['M','P','T']
total = set()
visited = set()
while stack:
X,time,how = stack.pop(0)
if time > result:
break
temp = [X-1,X+1,X*2]
for ind,k in enumerate(temp):
if 0<=k<=100000 and time+1<=result:
if dp[k] == -1 or dp[k] == time+1:
dp[k] = time+1
stack.append((k,time+1,how+dire[ind]))
if k == M:
result = time+1
total.add(how+dire[ind])
print(result)
print(len(total))
else:
print(0)
print(1)
처음에는 단순히 BFS처럼 풀어주었다. 결과값인 result를 큰 수로 설정해놓고, BFS를 하면, 최초로 변하는 값이 제일 작은 값이 되고, 출력되어야하는 값이 되니, result값보다 작은 time일때만 들어오게 설정해주었다. 그리고, 이 문제에서 처음에 틀렸던 이유 중 하나가, 같은 시간대에 정답에 올 수 있는 경우의 수가 많았다. 그래서 방문표시를 해주는 dp를 최초 방문이거나 아니면 time+1과 같을때, 같은시간대일때만 올 수 있도록 해줬다.
또한 전체적인 방법의 수를 찾기 위해, 이동방향을 저장해주는 로직을 추가해줬었다. 그래서 목표값 M에 도착을 하면, total에 추가를 해줘서, 전체 방법의 가지수를 찾아냈다.
하지만 이 방식의 문제점은, 시간이 오래걸린다는 점이다. 매번 BFS를 하는것과 같고, 그럼으로서 시간이 느릴수 밖에 없었다.
이와 같은 문제는 BFS이기도 하지만, 각각의 BFS를 하는것보다, 한 타임씩 맞춰서 한꺼번에 하는 편이 시간을 절약하는데 도움이 되는 것 같다.
# 12851 숨바꼭질
N,M = map(int,input().split())
times = 0
ways = 0
prev_vistied = {N : 1}
visited = [True]*100001
if N == M:
ways = 1
while not ways:
new_visited = {}
for number in prev_vistied:
for new_number in [number-1,number+1,2*number]:
if 0<= new_number <= 100000 and visited[new_number]:
if new_number == M:
ways += prev_vistied[number]
else:
if new_visited.get(new_number):
new_visited[new_number] += prev_vistied[number]
else:
new_visited[new_number] = prev_vistied[number]
for visited_number in new_visited:
visited[visited_number] = False
prev_vistied = new_visited
times += 1
print(times)
print(ways)
개선한 방식은 다음과 같다.
직전에 방문한 지점 prev_visited를 반복문을 돌리고, 방문하지 않았으면, new_visited에 prev_visited에서 누적된 해당 number에 올 수 있는 방법의 가지수를 더해주면 된다.
한번의 반복문이 끝나고 난뒤에, visited 함수에 방문을 한 것을 표시해주고, prev_visted를 new_visited로 변경시켜주면 된다.
이렇게 하면, 위의 BFS는 각각의 방법 하나하나마다 결과값에 도착할때까지 BFS를 하면서 반복문을 돌려야하지만, 이 방법은 number 단위로 해당 number에 올 수 있는 최소 타임을 이용해 한꺼번에, BFS를 한다는 점이다.
위와 같은 time을 세는 문제 같은 경우엔 일반적인 BFS가 아닌, 한 타임별로 전체를 반복문 돌리는 풀이방식도 생각해봐야겠다.
# 2251 물통
# A,B,C
# 앞의 두 물통은 비어 있고, 세번째 물통은 가득 차 있다.
# A 물통이 비어있을때 세번째 물통에 담겨 있을 수 있는 물의 양을 구해내시오.
import collections
max_Bowl = list(map(int,input().split()))
current_bowl = [0,0,max_Bowl[2]]
visited = [[[False]*(max_Bowl[2]+1) for _ in range(max_Bowl[1]+1)] for _ in range(max_Bowl[0]+1)]
# A,B,C
que = collections.deque()
que.appendleft((0,0,max_Bowl[2]))
result = set()
result.add(max_Bowl[2])
while que:
cureent_water = que.popleft()
if visited[cureent_water[0]][cureent_water[1]][cureent_water[2]]:
continue
if cureent_water[0] == 0:
result.add(cureent_water[2])
visited[cureent_water[0]][cureent_water[1]][cureent_water[2]] = True
# A->B
if cureent_water[0]+cureent_water[1] >= max_Bowl[1]:
que.append((cureent_water[0]+cureent_water[1]-max_Bowl[1],max_Bowl[1],cureent_water[2]))
else:
que.append((0,cureent_water[0]+cureent_water[1],cureent_water[2]))
# A->C
if cureent_water[0]+cureent_water[2] >= max_Bowl[2]:
que.append((cureent_water[0]+cureent_water[2]-max_Bowl[2],cureent_water[1],max_Bowl[2]))
else:
que.append((0,cureent_water[1],cureent_water[0]+cureent_water[2]))
# B->C
if cureent_water[1]+cureent_water[2] >= max_Bowl[2]:
que.append((cureent_water[0],cureent_water[1]+cureent_water[2]-max_Bowl[2],max_Bowl[2]))
else:
que.append((cureent_water[0],0,cureent_water[1]+cureent_water[2]))
# B->A
if cureent_water[1]+cureent_water[0] >= max_Bowl[0]:
que.append((max_Bowl[0],cureent_water[1]+cureent_water[0]-max_Bowl[0],cureent_water[2]))
else:
que.append((cureent_water[1]+cureent_water[0],0,cureent_water[2]))
# C->A
if cureent_water[2] + cureent_water[0] >= max_Bowl[0]:
que.append((max_Bowl[0],cureent_water[1],cureent_water[2]+cureent_water[0]-max_Bowl[0]))
else:
que.append((cureent_water[2]+cureent_water[0],cureent_water[1],0))
# C->B
if cureent_water[2] + cureent_water[1] >= max_Bowl[1]:
que.append((cureent_water[0],max_Bowl[1],cureent_water[2]+cureent_water[1]-max_Bowl[1]))
else:
que.append((cureent_water[0],cureent_water[2]+cureent_water[1],0))
result = sorted(list(result))
print(*result)
처음에 풀때 난잡하다. 똑같이 반복되는것을 계쏙 반복해주었다.
A->B,
A->C
B->C
B->A
C->A
C->B
의 과정을 거쳐주면서 방문하지 않은 경우에만 하는 방식으로 했다.
이렇게 하니 단순반복을 계속해서 쓰면서도 알아보기 힘들었다.
A,B,C = map(int,input().split())
def custom_append(a,b,c):
global visited,stack,result
if (a,b,c) not in visited:
visited.add((a,b,c))
stack.append((a,b,c))
if a == 0:
result.add(c)
def move_bowl(origin,target,target_max):
if origin+target >= target_max:
origin = origin+target- target_max
target = target_max
else:
target = origin + target
origin = 0
return (origin,target)
visited = set()
visited.add((0,0,C))
stack = [(0,0,C)]
result = set()
result.add(C)
while stack:
ca,cb,cc = stack.pop()
if ca:
# A->B
na,nb = move_bowl(ca,cb,B)
custom_append(na,nb,cc)
# A->C
na,nc = move_bowl(ca,cc,C)
custom_append(na,cb,nc)
if cb:
# B->C
nb,nc = move_bowl(cb,cc,C)
custom_append(ca,nb,nc)
# B->A
nb,na = move_bowl(cb,ca,A)
custom_append(na,nb,cc)
if cc:
# C->A
nc,na = move_bowl(cc,ca,A)
custom_append(na,cb,nc)
# C->B
nc,nb = move_bowl(cc,cb,B)
custom_append(ca,nb,nc)
result = sorted(list(result))
print(*result)
좀 더 깔끔하게 바뀐 풀이방식이다.
물을 옮기는 과정을 하나의 함수로 만들어주었고, stack에 추가해주고 방문표시를 해주는것도 하나의 함수로 만들어줬다.
# 입력 지폐의 금액 T 동전의 가지수 k 각 동전 하나의 금액 pi ni가 주어진다.
# 방법의 수는 2^31 -1 을 초과하지 않는다.
T = int(input())
k = int(input())
money = [list(map(int,input().split())) for _ in range(k)]
money.sort(reverse=True)
dp = (T+1)*[0]
dp[0] = 1
for coin_val,coin_cnt in money:
for current_money in range(T,1,-1):
for current_cnt in range(1,coin_cnt+1):
if current_money - current_cnt*coin_val >= 0:
dp[current_money] += dp[current_money-current_cnt*coin_val]
print(dp[T])
DP 관련 문제였다. 풀고보니 평범한 배낭과 비슷한 로직이었다. 거기서는 가치를 판단하여, 가치값의 최대를 찾는거였다면, 여기는 방법의 가지수를 찾는 것이라 다르지만, 하나의 dp를 이용해 역으로 진행하면서, 누적시켜주는 것에 있어서 비슷하다고 봤다.
기본적이 원리는 다음과 같다.
동전의 가지수 k개가 주어지면,
첫번째 동전으로 만들 수 있는 모든 동전의 종류를 만들어 본다.
그리고 두번째 동전으로 만들 수 있는 모든 동전의 종류를 만들어서 누적시켜준다.
이렇게 k번을 반복을 해준다.
여기서 주의해야할 점은 아래에서 위로 올라가면, 이전에 만들어진 것 때문에, 원치 않는 결과가 나올 수 있으므로,
주어진 목표 금액인 T에서 -1씩 줄여주면서 다이나믹 프로그래밍을 해준다.
여기서 평범한 배낭과 또 다른 점은, 같은 동전이 여러개 존재하는 것이다.
그래서 동전의 개수 n개만큼 반복을 시켜주면서 진행해야한다.
즉 3원짜리 동전이 5개가 있다하면,
1회차 // 2회차
T - 3*1 ,| (T-1) - 3*1, ....
T - 3*2, |(T-1) - 3*2 ,...
T - 3*3, |(T-1) - 3*3, ...
T- 3*4, |(T-1) - 3*4 .....
T - 3*5, |(T-1) - 3*5 ....
이렇듯 동전의 개수만큼 진행시켜줘야, 그 동전으로 만들 수 있는 모든 경우를 탐색할 수 있다.
여기서 또 주의해야할 점은 T는 동전의 개수를 조정하는 반복문 밖에 있어야한다.
원래 DP에 약하기도 했지만 비슷한 문제를 풀어본 경험이 있었는데도, 푸는데 시간이 오래걸렸다.
이전에 풀었던 문제들도 다시 공부하여, DP에서 필요한 점화식을 빨리 구하는데 노력해야겠다.
