n=int(input())
card=[0]
card+=list(map(int,input().split()))
dp=[0]*(n+1)
dp[1]=card[1]
dp[2]=max((card[2],card[1]*2))
for i in range(3,n+1):
dp[i]=card[i]
for j in range(1,i//2+1):
dp[i]=max(dp[i],dp[j]+dp[i-j])
print(dp[n])
초창기에 풀었던 문제이다.
현재 DP에서의 초기값을 넣어주고, 두개를 더해서 i가 되는 경우를 갱신해주면 된다.
J의 range(i//2+1)인 이유는 중간까지 하면, 그 다음부터는 앞의것의 반복이기 때문이다.
# 17086 아기 상어
import collections
dx = [-1,0,1,-1,1,-1,0,1]
dy = [-1,-1,-1,0,0,1,1,1]
def bfs(x,y):
deque = collections.deque()
deque.append((x,y,0))
visited = [[True]*M for _ in range(N)]
visited[x][y] = True
while deque:
x,y,cnt = deque.popleft()
if arr[x][y]:
return cnt
for i in range(8):
nx = x + dx[i]
ny = y + dy[i]
if 0<= nx <N and 0<=ny <M:
if visited[nx][ny]:
deque.append((nx,ny,cnt+1))
visited[nx][ny] = False
N,M = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(N)]
result = 0
for x in range(N):
for y in range(M):
if not arr[x][y]:
temp = bfs(x,y)
result = max(temp,result)
print(result)
처음에는 각 점에서 BFS를 해서 상어와의 위치값이 가장 먼 값을 구하는 방법을 했다.
import collections
dx = [-1,0,1,-1,1,-1,0,1]
dy = [-1,-1,-1,0,0,1,1,1]
N,M = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(N)]
shark = collections.deque()
for i in range(N):
for j in range(M):
if arr[i][j] == 1:
shark.append((i,j,arr[i][j]))
while shark:
x,y,dis = shark.popleft()
for i in range(8):
nx = x + dx[i]
ny = y + dy[i]
if 0<= nx <N and 0<=ny<M:
if not arr[nx][ny]:
arr[nx][ny] = 1
shark.append((nx,ny,dis+1))
print(dis-1)
두번째 풀이는 그 반대로, 상어를 기준으로 bfs를 진행했다. 어차피 bfs는 거리순으로 진행되기 때문에, 가장 마지막에 나오는 dis가 최대 거리이므로, 마지막 dis에서 1을 빼줬다.
# 5569 출근경로
# 남북방향 도로 w개 동서 방향 도로가 h개
# 남북방향은 서쪽부터 1,2,....w
# 동서도 남쪽부터 1....h
# 교차로 (i,j)
# 1번 이후부터 가능
w,h = map(int,input().split())
dp = [[[[0]*2 for _ in range(2)] for _ in range(h)] for _ in range(w)]
# 3번째 인덱스 0 북쪽, 1은 동쪽
# 4번째 인덱스는 방향전환 여부 1이 가능 0이 불가능
# 자세한 설명을 하자면, 3번째 인덱스는 그 전 위치에서 올라온 방향을 나타내는 것이다.
# 3번째 인덱스가 0 이면 x-1,y의 위치에서 북쪽으로 올라왔을때를 말한다.
# 4번째 index는 현재 x,y 좌표에 있는 값이 회전이 가능한지에 대해 적어놓은것이다.
# 1이면 회전이 가능한 것이고, 0이면 회전이 불가능한 것이다.
# 처음에, x=0일때와 y=0일때 초기화 작업을 해준다.
for i in range(1,w):
dp[i][0][0][1] = 1
for i in range(1,h):
dp[0][i][1][1] = 1
for x in range(1,w):
for y in range(1,h):
# (x,y) 좌표에서 3번째 index가 0 인 경우는 (x-1,y)에서 온 경우이다.
# 여기서 회전이 가능할때와 불가능할때를 구분해서 해야한다.
# 회전이 불가능한 경우는 (x-1,y) 위치에서 3번째 index가 1이고, 네번째 index가 1인경우이다.
# 동쪽에서 오고, 회전이 가능할때이다. 북쪽으로 방향이동을 할수 있고, 그 다음에는 방향을 전환할수 없기 떄문이다.
# 회전이 가능한 경우는 (x-1,y) 기준으로 3번째 index가 0인 경우 전부이다.
# 왜냐하면 (x-1,y)에서 3번째 index가 0인경우는 (x-2,y)에서 온 경우이므로, 어떠한 경우에서도 회전이 가능하기 때문이다.
dp[x][y][0][0] = dp[x-1][y][1][1]
dp[x][y][0][1] = dp[x-1][y][0][0] + dp[x-1][y][0][1]
# (x,y) 좌표에서 3번째 index가 1인 경우는 (x,y-1)에서 온 경우이다.
# 여기서 회전이 가능할때와 불가능할때를 구분해야한다.
# 회전이 불가능한 경우는 (x,y-1) 위치에서 3번째 index가 0이고, 네번째 index가 1인 경우이다.
# (x,y-1)으로 올때 (x-1,y-1)에서 올라와서 방향전환을 (x,y-1)에서 해서 방향전환을 할 수 없기때문이다.
# 회전이 가능한 경우는 (x,y-1) 위치에서 3번째 index가 1인 모든 경우이다.
dp[x][y][1][0] = dp[x][y-1][0][1]
dp[x][y][1][1] = dp[x][y-1][1][0] + dp[x][y-1][1][1]
result = sum(dp[w-1][h-1][0]) + sum(dp[w-1][h-1][1])
print(result%100000)
다이나믹 프로그래밍를 이용해 푼 문제 중에서 내게 어려웠던 문제였다.
DP를 잘 모르는 상태에서 DP를 어떻게 설계를 해서, 저장시켜놓을지가 고민이었다.
그리고 여기서 좀 헷갈렸던 것이, DP에 이전 위치에서 올라온 방향을 저장해주는 3번째 index와, 회전이 가능한지 구분해주는 4번쨰 index가 헷갈렸다.
회전이 가능한 것은 현재 (x,y) 좌표에서 회전 가능여부를 보는 것이고, 3번째 index는 그 전 위치에서 북쪽에서 왔는지 동쪽에서 왔는지 구분해줘야했다.
서로 다른 기준점으로 인해, DP를 설계하는데 어려움을 겪었다.
위의 코드의 주석에서도 설명했지만, 총 4가지 경우를 나누어서, 정리해야한다.
1. 이전 위치에서 북쪽으로 이동해서 도착했고,, 다음번에 회전이 가능한 경우
2. 이전 위치에서 북쪽으로 이동해서 도착했고, 다음번에 회전이 불가능한 경우
3. 이전 위치에서 동쪽으로 이동해서 도착했고, 다음번에 회전이 가능한 경우
4. 이전 위치에서 동쪽으로 이동해서 도착했고,다음번에 회전이 불가능한 경우
1번 경우를 설명하자면, (x,y) 위치에 올때, 북쪽으로 이동해서 도착하고, 회전이 가능할려면, (x-1,y)에서 와야하며, 거기서도 북쪽으로 도착해야지만, 쭉 직진으로 온거기 때문에 회전이 가능하다.
이러한 경우는 [x-1][y][0][0]와 [x-1][y][0][1] 이다. 인덱스를 분석하면
[x-1][y][0][0]은 x-2,y의 위치에서 x-1,y로 북쪽으로 해서 왔고, x-2,y의 위치에서 이미 방향을 전환했기때문에, x-1,y에서 방향전환을 못하는 빨강색 화살표를 의미한다.
[x-1][y][0][1] 은 x-2,y의 위치에서 x-1,y로 북쪽으로 해서 왔고, x-2,y에서 방향전환을 안하고 왔기 때문에, x-1,y의 위치에서 방향전환이 가능한 파랑색 화살표를 의미한다.
그러므로 [x][y][0][1] = [x-1][y][0][0] + [x-1][y][0][1] 이다.
2번 경우는 (x-1,y)에서 방향전환을 해서 (x,y)를 왔기 때문에 다음번에 회전을 못하는 경우이다.
이런 경우는 (x-1,y)에서 동쪽에서 왔고, (x-1,y)에서 회전이 가능한
[x-1][y][1][1] 일때, [x][y][0][0]이 될수 있다.
3,4번 경우는 위를 회전한 것이다.
그림이 조잡해서 약간 이해하기 힘들지만, 위와 같이 총 4가지 경우를 나누어서 dp를 하면 된다.
def dfs(bomblist):
global N,result
while bomblist:
x,y = bomblist.pop()
for i in range(8):
nx = x + dx[i]
ny = y + dy[i]
if (nx == 0 or nx == N-1) or (ny == 0 or ny ==N-1):
if arr[nx][ny] == 0:
break
else:
for i in range(8):
nx = x + dx[i]
ny = y + dy[i]
if (nx == 0 or nx == N-1) or (ny == 0 or ny ==N-1):
arr[nx][ny] -= 1
result += 1
return
N = int(input())
dx = [-1,0,1,-1,1,-1,0,1]
dy = [-1,-1,-1,0,0,1,1,1]
arr = [list(input()) for _ in range(N)]
result = 0
if N >4:
result += (N-4)**2
bomb = []
for x in range(N):
for y in range(N):
if x == 1 or x == N-2:
if arr[x][y] == '#':
bomb.append((x,y))
else:
arr[x][y] = int(arr[x][y])
elif 1<x<N-2:
if y == 1 or y == N-2:
bomb.append((x,y))
else:
if arr[x][y] != '#':
arr[x][y] = int(arr[x][y])
else:
if arr[x][y] != '#':
arr[x][y] = int(arr[x][y])
dfs(bomb)
print(result)
지뢰찾기를 하는 문제이다. 테두리에만 숫자가 있고, 그 안은 파악되지않는 지뢰구역이 있다.
이 지뢰구역에서 최대로 설치가능한 지뢰의 개수를 구하는 문제이다.
먼저, 테두리에 직접적으로 닿아있는 칸들을 제외한 나머지 칸들은 전부 지뢰가 있다고 가정을 해야, 최대 지뢰를 구할 수 있다.
그리고 두번째로 테두리에 근접해있는 칸들을 기준으로 8칸을 탐색을 해서, 그 안에 0이 있다면, 해당 구역은 지뢰가 존재할수 없는 공간이니 넘어간다.
하지만, 0이 존재하지 않는 경우 지뢰가 존재하는 경우이니, 지뢰의 수를 1개 늘려주고, 해당 구역의 주변 8칸의 숫자를 1씩 줄여준다.
이걸 반복해준다.
여기서 쓴 코드적인 부분은 for else 문이다.
for문을 반복하면서, break를 한번도 마주치지 않으면 자동적으로 else문이 실행되는 것이다.
# 1058 친구
def dfs(idx):
global N
visited = [True]*N
visited[idx] = False
stack = [(idx,0)]
cnt = -1
while stack:
cu_x,both_person = stack.pop()
for x in range(N):
if arr[cu_x][x] == 'Y':
if visited[x] and both_person <= 1:
visited[x] = False
stack.append((x,both_person+1))
cnt += 1
return cnt
N = int(input())
arr = [list(input()) for _ in range(N)]
max_number = 0
for i in range(N):
temp = dfs(i)
max_number = max(max_number,temp)
print(max_number)
이 문제는 DFS를 이용해서 풀었다.
이 문제에서 2-친구가 되는 경우는 2종류이다.
1. 직접적인 친구인 경우
2. 한 다리를 건너서 친구가 되는 경우
총 2가지이다.
이것을 구분해주기 위해 both_person이라는 변수로 징검다리 친구가 되는 경우를 찾아줬따.
이 변수 없이 진행 시, 연결된 모든 친구들이 출력되기 때문에, 최대 거리가 2이하인 경우만 구분해줄려고 썼다.
이 문제를 풀고 난뒤에 대부분의 사람들이 플로이드 와샬로 풀었다는 경우가 많지만,
아직 플로이드 와샬 알고리즘에 대해 잘 모르기 때문에 그 방법은 나중에 알고리즘을 배우면 시도 해봐야겠다.
N = int(input())
dp = [[0]*10 for _ in range(N)]
temp = [-1,1]
for i in range(N):
for j in range(10):
if i == N-1:
if j == 0:
continue
if i == 0:
dp[0][j] = 1
else:
for k in temp:
nx = j+k
if 0<=nx<10:
dp[i][j] += dp[i-1][j+k]
print(sum(dp[N-1])%1000000000)
dp 관련 문제이다.
이전 x-1축과 x축의 j 값이 1이 차는 경우를 더해주면 되는 것이다. 그리고 마지막 N-1 축까지 왔을 때 그때까지 누적된 수를 더해주면 된다.
# 1149번 RGB 거리
# RGB 거리엔 N개의 집 1~N 순서대로
# 빨 초 파 중 하나
# 비용의 최소값 구하기
# 1번집의 색 != 2번집의 색
# N번집의 색은 N-1 번집의 색과 같지 않아야한다.
N = int(input())
# RGB
arr = [list(map(int,input().split())) for _ in range(N)]
INF = float('inf')
dp = [[INF] *3 for _ in range(N)]
for i in range(3):
dp[0][i] = arr[0][i]
for x in range(1,N):
for y in range(3):
for z in range(3):
if y != z:
dp[x][y] = min(dp[x][y],dp[x-1][z]+arr[x][y])
print(min(dp[N-1]))
처음엔 그냥 dfs를 이용해서 풀어볼려다가, 입력 N이 1000까지라, 3^1000은 시간초과가 날것 같아서 dp로 선회했다.
dp에서 제일 어려운건 동적프로그래밍을 저장할 공간을 설계하는 것 같다. 이 문제를 풀때에 어떻게하면, 이전위치의 저장정보와 최소값 저장할지 고민했었다.
그 해결방법으로 index를 이용했다. dp를 저장하는 y축 index가 동일하지않으면 된다는 점을 착안하여, dp를 설계했다.
