[코딩테스트]#8. 백준 1010번,11052번,1904번

1. 1010번: 다리놓기

-문제: https://www.acmicpc.net/problem/1010

1010번: 다리 놓기

어렵게 생각했는데 알고보니 조합 문제였던; 수학적으로 생각해보는 것도 해보고, 단순하게 생각할 수 있으면 최대한 그렇게 해보자

 

-정답풀이: 

• 조합 구하는 식 알아두기 

 

2. 11052번: 카드 구매하기

-문제: https://www.acmicpc.net/problem/11052

11052번: 카드 구매하기

문제는 이해했으나 구현이 어려웠음.

 

-정답풀이: 

n=int(input())
d=[0]*(n+1)
p=[0]+list(map(int,input().split()))
d[1]=p[1]
for i in range(2,n+1):
    for j in range(1,i+1):
        if d[i]<d[i-j]+p[j]:
            d[i]=d[i-j]+p[j]
print(d[n])

다른 블로그 참조해서 이해한 결과 

d[i]에서 i는 구매하는 카드의 개수이고 다음과 같은 규칙을 가진다.

d[1]=p[1] (카드를 하나 구매하면 당연히 카드 한개의 가격의 가짓수이다)

d[2]=d[0]+p[2], d[1]+p[1](1개카드 두개 구매하는거)

d[3]=d[0]+p[3], d[1]+p[2], d[2]+p[1]

d[4]=d[0]+p[4], d[1]+p[3],d[2]+p[2],d[3]+p[1]

 

3. 1904번: 01타일 

-문제: https://www.acmicpc.net/problem/1904

1904번: 01타일

피보나치 수열로 쉬운 문제였다

 

-정답풀이: 

-틀린 풀이: 

• 리스트 다 구하고 15746으로 나누니 메모리 초과 발생. append할 때 나누어서 넣어야한다
• 그리고 1자리 수에 00은 불가능하지만, 1은 가능하므로 1의 값을 가진다(초기값 설정하는데 생각 더하자)