꼬인 전깃줄
4일 전에 블로그 해설을 보고 풀었던 꼬인 전깃줄 문제를 다시 풀었다. 언제나 그렇듯 이제 알았다고 생각했지만, 다시 풀어보니 또 다시 힘들었다.
답, 풀이 방향을 모두 아는상테에서 푸는데도 힘들다는게 참,,, 실력이 느는게 쉽지 않구나 하고 다시 느낀다. 꾸준히 풀어 나가자!
CODE
import sys
read=sys.stdin.readline
n=int(read())
num=list(map(int,read().split()))
save=[num[0]]
def bin_search(x):
m=len(save)
l,r=0,m-1
while True:
mid=(l+r)//2
if save[mid]>x:
if 1<=mid and save[mid-1]<x:
save[mid]=x
break
elif save[0]>x:
save[0]=x
break
else: r=mid-1
else: l=mid+1
for i in num[1:]:
if save[-1]<i: save.append(i)
else: bin_search(i)
print(n-len(save))
1, 2, 3 더하기 7
잘 풀어놓고, 이상한데서 헤맸다. 처음에 숫자쌍을 dictionary로 받았는데, 이렇게 되면 아래와 같은 문제가 생겼다. 입력이
3
4 3
2 1
4 2
이렇게 들어오는 경우 순서대로 출력할 수 없게되는 문제가 있었다. 이 생각을 못해서 30분을 잡아먹었다. 전체적으로 평범한 dp 문제였다.
CODE
import sys
read=sys.stdin.readline
n=int(read())
answer=[]
m=0
for _ in range(n):
a,b=map(int,read().split())
answer.append([a,b])
m=max(a,m)
dp=list(list(0 for _ in range(m+1)) for _ in range(m+1))
dp[1][1]=1
if m>1:
dp[2][1]=1
dp[2][2]=1
if m>2:
dp[3][1]=1
dp[3][2]=2
dp[3][3]=1
#check=1
for i in range(4,m+1):
for j in range(1,i+1):
dp[i][j]=(dp[i-1][j-1]+dp[i-2][j-1]+dp[i-3][j-1])%1_000_000_009
#if dp[i][j]==0: check+=1
for a,b in answer:
print(dp[a][b])
풀어야 할 문제
- 스타트 택시
- 미네랄
- 회전 초밥
- 아기 상어
- 전깃줄 -2