백준 9184
import sys
def DFS(a,b,c) :
if a <= 0 or b <= 0 or c <= 0 :
return 1
elif a > 20 or b > 20 or c > 20 :
return DFS(20,20,20)
if dp[a][b][c] :
return dp[a][b][c]
elif a < b and b < c :
dp[a][b][c] = DFS(a, b, c-1) + DFS(a, b-1, c-1) - DFS(a, b-1, c)
else :
dp[a][b][c] = DFS(a-1, b, c) + DFS(a-1, b-1, c) + DFS(a-1, b, c-1) - DFS(a-1, b-1, c-1)
return dp[a][b][c]
dp = [[[0 for _ in range(21)] for _ in range (21)] for _ in range (21)]
while True:
a,b,c= map(int,sys.stdin.readline().split())
if a == -1 and b == -1 and c == -1 :
break
print ("w({}, {}, {}) = {}".format(a,b,c,DFS(a,b,c)))
문제를 쉽게 접근하였지만, 매번 20번이면 8000개 의 연산을 계속해서 진행해야 되었기 떄문에
문제가 발생했다.
이를 위해 dp라는 3차원 배열을 만들어, 기록된 정보가 있으면 다시 그 연산을 진행하지는 않게 변경하였다.
#추가 주의 tip!
문자열에 원하는 변수를 출력하기 위해
print("x를 출력합니다 {x}".format(x))로 {x}안에 x를 출력할 수 있다.
백준 1912
import sys
N = int(sys.stdin.readline())
Nlist = list(map(int,sys.stdin.readline().split()))
for i in range(1,N) :
Nlist[i] = max(Nlist[i],Nlist[i]+Nlist[i-1])
print(max(Nlist))
문제 자체는 쉬웠으나, 이를 생각해내는 과정이 굉장히 어려웠다.
배열에서 연속된 수를 구한다면, 가장 처음부터 시작해서
a b c d e f g 일시
b는 a+b나 b중 더 큰 값을, c는 c나 (a+b나 b중에서 큰값으로 결정된 b)+c인 값을 구해서 이를 계속 대입하면 된다.
Dp라는 것은, 동적 계획법의 의미로써 한번 계산한 것을 다시 계산하지 않게끔 하는 의미이다.
Dp로 기억하는 행렬을 만드는 방법만 이있는 것이 아니라, 한번 한 계산을 다시 하지 않음에 주의하자.
*특히 이문제는 1초에 추가시간없음 으로 , 시간에 대한 문제임을 어느정도 힌트로 준 문제였다.
*메모리또한 매우 작은 문제였다. 그리고 특이 경우가 없어서 한 LIST로 해결할 수 있다.
백준 1149
import sys
N = int(sys.stdin.readline())
graph = [[0]]+[[0]+list(map(int,sys.stdin.readline().split())) for _ in range (N)]
colorgraph = [-1] * (N+1)
#VISITED 로도 쓰자
minpay = 10000000000000
def DFS (index) :
global minpay
if index == N :
sumcolor = 0
for i in range(1,N+1) :
whatcolor = colorgraph[i]
sumcolor = sumcolor+ graph[i][whatcolor]
minpay = min(minpay,sumcolor)
return
if index>0 and colorgraph[index] == colorgraph[index-1] :
return
for i in range(1,4) :
if colorgraph[index+1] == -1 :
colorgraph[index+1] = i
DFS(index+1)
colorgraph[index+1] = -1
DFS(0)
print(minpay)
도움 없이 풀고 모든 case를 통과해서 매우기뻤지..만!
역시나 시간초과가 발생했다 .
(문제의 시간제한이 0.5초였고, 이는 곧 일반적인 생각보다 한단계가 더있어야 한다는 의미였을 것이다 )
import sys
N = int(sys.stdin.readline())
graph = [ list(map(int,sys.stdin.readline().split())) for _ in range(N) ]
for i in range(1,N) :
graph [i][0] = min(graph[i-1][1],graph[i-1][2])+ graph[i][0]
graph [i][1] = min(graph[i-1][0],graph[i-1][2])+ graph[i][1]
graph [i][2] = min(graph[i-1][0],graph[i-1][1])+ graph[i][2]
print(min(graph[N-1]))
답안을 찾아보다 놀랐다.
*현재까지 , 또 많은 사람들이 DFS , BFS문제를 풀다보면 그 꼴에 맞추어 생각하여
트리를 그리고..이런식으로 푼다.
하지만 시간 제한이 강하게 걸려있다면, 다른 풀이가 있는 것을 의심해보도록 하자.
이번 DP문제도 이전까지의 결과를 내 현재 결과에 저장하는 식으로 문제를 풀면 가능한 경우였다.
이번 경우또한, 현재까지 찾은것이 미래에도 최선의 결과가 되는 문제이다.
즉 이러한 강한 제약시는, GREEDY 알고리즘인지를 파악하자 !
백준 2579
import sys
input = sys.stdin.readline
n = int(input())
stairs = [0] * 301
for i in range(1, n + 1):
stairs[i] = int(input())
dp = [0] * 301
dp[1] = stairs[1]
dp[2] = stairs[1] + stairs[2]
dp[3] = max(dp[1] + stairs[3], stairs[2] + stairs[3])
for i in range(4, n + 1):
dp[i] = max(dp[i - 3] + stairs[i - 1] + stairs[i], dp[i - 2] + stairs[i])
print(dp[n])
문제를 틀렸었는데, 그 이유는 별도의 dp를 지정하지 않고 stairs에 값을 넣는 형태로 풀려 해서이다.
이문제는, 3번연속으로 같은곳을 갈 수 없다는 특이 조건이 있고,
1~3까지는 또 기존과 다르게 가며,
가장 결정적으론 5에서 봤을때 3에서 부터 새로 갈것인지, 혹은 2 , 45로 새로 갈 것인지를 정해야한다.
즉 시간이 매우 부족하거나 메모리가 매우 적은 문제가 아니라면, 별도의 DP를 지정해서 푼다.
*DP 문제의 해결 TIP - 몇번의 INDEX를 적어주고, 그 INDEX가 어디에서 왔는지를 판단한다.
*가중치가 있다면, 별도의 행렬이 필수적이다.
백준 1463
시간제한 0.15를 보자마자, 모든 경우의 수를 찾는것이니 DFS를 하려던 생각을 포기했다.
import sys
N = int(sys.stdin.readline())
cnt = 0
Nlist = [ 0 for _ in range(N+1) ]
for i in range(2,N+1) :
Nlist[i] = Nlist[i-1]+1
if i %3 == 0 :
Nlist[i] = min(Nlist[i],Nlist[i//3]+1)
if i %2 == 0 :
Nlist[i] = min(Nlist[i],Nlist[i//2]+1)
print(Nlist[N])
여태까지 풀었던 재귀 문제들과 유사한데, 한가지 생각하지 못한 점은
1) 모든 연산이 동일하게 이루어지고 ,특이 CASE 도 없기 때문에 작성할 필요가 없다.
2) 가중치가 없기 떄문에 DP로 새 행렬을 만들어도 동일하게 한 행렬만 사용한다.
3) 이 개념을 생각 못한 이유가 가장 큰데,
어디서 왔는지를 판단하는 기준을 1로 만들어 갈때가 아닌, 1부터 입력받은 N으로 가는 것으로 반대로 생각했어야 한다.
백준1904
import sys
N = int(sys.stdin.readline())
dp = [-1]* (N+1)
dp[1] = 1
if N >=2 :
dp[2] = 2
for i in range(3,N+1) :
dp[i] = (dp[i-1]+dp[i-2])%15746
print(dp[N])
1) 몇번의 경우는 , 진행해보는 것을 반드시 우선적으로 하자
2) 시간초가 짧은것을 확인하고 dp로 푼 시도는 좋았다, 특이 case인 1의 경우도 잘 골라냈다
3) 하지만, 메모리 공간이 부조갷ㅆ고 이는 n이 10000000ㄲ지 올 수 있기 떄문에 , %로 나눠 값의 메모리를 적게 할당하자.
