백준 1793
import sys
dp = [ 0 for _ in range(251)]
dp[0] = 1
dp[1] = 1
dp[2] = 3
for i in range(3,251) :
dp[i] = dp[i-1] + (dp[i-2]*2)
while(True) :
try :
N= int(sys.stdin.readline())
print(dp[N])
except:
break
2*N을 채우는 방법은, dp[i-1] (전 거를 채우는 방법 + 세로로 한줄) + dp[i-2]*2(3개가 아니라 2개인 이유는, 다 세로인 경우는 앞에 포함된다.
로 쉽게 풀었다.
자꾸 java와 혼동하여 try catch로 하는데, try : except:임을 기억하자.
백준 1003
import sys
dp = [0] * 41
dp[1] = 1
zerosum = 0
onesum = 0
def DFS(N) :
global zerosum
global onesum
if (N == 0) :
zerosum += 1
return 0
elif N == 1:
onesum += 1
return 1
else :
return DFS(N-1)+DFS(N-2)
T = int(sys.stdin.readline())
for i in range(T) :
zerosum = 0
onesum = 0
DFS(int(sys.stdin.readline()))
print(zerosum,onesum)
# else 후에 return이 큰 의미는 없지만, 그렇다고 빼면 한 함수에서 return이 2개로 분기되는 현상이 발생해 오류가 생긴다.
이와 같이 코드를 작성하였지만, 시간제한 0.25초에 따라 당연하게 시간 제한이 걸렸다.
백준 1003번
import sys
dp = [[0,0] for _ in range(41)]
dp[0] = [1,0]
dp[1] = [0,1]
T = int(sys.stdin.readline())
for i in range(T) :
zerosum = 0
onesum = 0
N= int(sys.stdin.readline())
for j in range(2,N+1):
dp[j][0] = dp[j-1][0]+dp[j-2][0]
dp[j][1] = dp[j-1][1]+dp[j-2][1]
print(dp[N][0],dp[N][1])
0과 1의 호출 수를 dp에 저장하여, 이를 return하는 형태로 구현하였다.
백준 9465
import sys
T =int(sys.stdin.readline())
for i in range(T) :
N = int(sys.stdin.readline())
Narr = [ list(map(int,sys.stdin.readline().split())) for _ in range(2) ]
dp = [ [0] * N for _ in range(2) ]
if N == 1 :
print(max(Narr[0][0],Narr[1][0]))
continue
elif N == 2:
print(max(Narr[0][0]+Narr[1][1],Narr[1][0]+Narr[0][1]))
continue
else:
dp[0][0] = Narr[0][0]
dp[1][0] = Narr[1][0]
dp[0][1] = Narr[1][0]+Narr[0][1]
dp[1][1] = Narr[0][0]+Narr[1][1]
for i in range(2,N) :
dp[0][i]= max(dp[1][i-2],dp[1][i-1])+Narr[0][i]
dp[1][i]= max(dp[0][i-2],dp[0][i-1])+Narr[1][i]
print(max(dp[0][-1],dp[1][-1]))
DP문제를 풀때, 전 값이 어디서 나오는지를 고민하는 것 까진 잘 했다.
하지만 DP 문제의 최댓값을 풀때는 주로
DP[I][X] = MAX(이전에서 올지, 어디서올지) + NARR[I][X]임을 다시 기억하면 좋을 것 같다.
해당 경우는 DP를 채우는 경우의 수가 2가지가 있엇으며,
처음과 두번쨰의 경우엔 해당 방식으로 채울수가 없기도 했다.
백준 1890
import sys
N = int(sys.stdin.readline())
Narr = []
for i in range(N) :
Narr.append(list(map(int,sys.stdin.readline().split())))
dp = [ [0]*N for _ in range(N) ]
cnt = 0
def DFS(x,y) :
global cnt
if x < 0 or y < 0 or x >= N or y >= N:
return
if Narr[x][y] == 0:
cnt += 1
return
else :
DFS(x+Narr[x][y],y)
DFS(x,y+Narr[x][y])
return
DFS(0,0)
print(cnt)
경로를 계산하는 것은, 항시 dfs 로 해왔기 떄문에 dfs를 하였지만, 이는 너무 많은 시간 복잡도가 생겼다.
O ( 2 의 100승 ) ..
<경로의 수를 계산하는 것을, dp로 구현해보자>
import sys
sys.setrecursionlimit(1000000)
N = int(sys.stdin.readline())
Narr = []
for i in range(N) :
Narr.append(list(map(int,sys.stdin.readline().split())))
dp = [ [0]*N for _ in range(N) ]
dp[0][0] = 1
cnt = 0
for i in range(N) :
for j in range(N) :
if (i == N-1) and (j == N-1) :
print(dp[i][j])
if i + Narr[i][j] < N :
dp[i + Narr[i][j]][j] += dp[i][j]
if j + Narr[i][j] < N :
dp[i][j+ Narr[i][j]] += dp[i][j]
이를 정리하면,
다음 dp에는, 해당 위치 (ex(받은arr의[i][j])에, 전에 다른 위치에서 몇번 왔는지를 정리할 수 있다.
즉, 이동하는 값은 -> narr에서
dp에는 -> 그 점까지 왔던 방법을 적는다.
백준 1309
import sys
N = int(sys.stdin.readline())
Narr = list(map(int,sys.stdin.readline().split()))
dp = [1] * N
for i in range(N) :
for j in range(0,i) :
if Narr[i]>Narr[j] :
dp[i]= max(dp[i],dp[j]+1)
print(max(dp))
dp를 선별하는 tip
1. 시간복잡도가 1000000 이 넘는가? - >dfs는 2의 n승으로 감에 주의 (주로 최대 최소)
2. 그렇다면, 재귀식이 나오는가?
3. 이 재귀식은, dp array내부적인 재귀일수도 있지만 손으로 풀어보니 답이 재귀의 형태일 가능성도 있다.
이 기준으로, dp문제임은 쉽게 알아냈지만, 재귀식을 찾는것이 어려웠다.
간단하게, j까지 자기보다 작은것이 몇개인지를 처음부터 적어가면 되는 구조였다!
1->5->3->7시, 1부터(j)n까지(i)로 찾아가게되면, 1,5,7 1,3,7과 같이, 자기보다 작은 애들중 순서가 맞는 애들이 자동으로 나오게 된다.
그렇다면, 재귀식은 어떻게 구할것인가
1. 1부터 직접 진행한다.
2. 일정 수 (보통 3~4)까지 진행하고, 재귀식이 나오나 본다.
3. 나오지 않지만 논리상 관계가 있어보인다면, 이를 고민한다(이 과정이 어려운 문제이다)
import sys
N = int(sys.stdin.readline())
dp = [1] * (N+1)
if N != 1:
dp[2] = 2
for i in range(3,N+1):
dp[i] = dp[i-1]+dp[i-2]
M = int(sys.stdin.readline())
doit = True
if M == 0 :
print(dp[N])
doit = False
answer = 1
lastnumber = 0
for i in range(M) :
#i는 안씁니다
inputnumber = int(sys.stdin.readline())
plusnumber = inputnumber-lastnumber-1
answer = answer * dp[plusnumber]
lastnumber = inputnumber
if i == (M-1):
answer = answer*dp[N-inputnumber]
if doit :
print(answer)
문제를 풀다보니, 80퍼 이상에서 문제가 발생했다 (indexerror)
이럴땐 반례를 생각하자는 경험이 있어 반례를 보았다.
1. N이 1일때
2. m이 0일때
해결하고 나니, 쉽게 풀 수 있었다.
