꼬인 전깃줄

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