[코딩테스트] #7. 백준 10844번,2193번,11727번

1. 10844번: 쉬운 계단수

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

10844번: 쉬운 계단 수

: 숫자가 한개일 때 쉬운 계단수를 못 구한하지 않나?라는 생각에 쉬운 계단수라는 개념이 처음에 이해가지 않았음. 

숫자가 한개일 때는 그냥 하나로 세고, 숫자길이 2일 때부터 생각하면됨. 이후 3부터는 숫자 길이 1,2일 때의 반복임을 이용하면된다.

 

-정답 풀이:

 

n=int(input())
dp=[[0 for i in range(10)] for j in range(101)]

#숫자가 무엇이든간에 자릿수가 1이면 계단수 1개임을 의미함 
for i in range(1,10):
    dp[1][i]=1
    
for i in range(2,n+1):
    for j in range(10):
        #i위치에 0이 오면 전행의 1의 개수와 동일하다(1의 -1이 0)
        if j==0:
            dp[i][j]=dp[i-1][1]
        #i위치에 9가오면 이전위치에 8밖에 못옴. 전행의 8의 개수와 동일    
        elif j==9:
            dp[i][j]=dp[i-1][8]
        else:
            dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1]
print(sum(dp[n])% 1000000000)

-그리고 오타 조심하기!!!  print를 priint라고 서서 NameError 엄청냄,,

 

2. 2193번: 이친수

**처음으로 풀이 안보고 맞힌 문제(피보나치 유형), 겉모습은 다르지만 점화식을 구해보면 피보나치 구조를 가지므로, 구현해서 답을 구함.

복잡해보이지만 알고보면 단순한 문제 

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

2193번: 이친수

 

-정답풀이:

• for문의 끝 인덱스가 n+1인 이유: 길이가 n인 이진수를 구하므로 n번째 인덱스 값을 출력해야하기 때문이다

 

-틀린풀이: 초기값이랑, 인덱스 조심(이거 꼭 제대로 하고 넘어가기)

 

 

3. 11727번: 2xn 타일링2(ssafy공부할 때 있었던 문제)

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

11727번: 2×n 타일링 2

: 인덱스를 잘못구해서 오류가 많았음. 점화식은 옳게 구함-> 인덱스 똑바로 정하는 연습하기. 해당문제 다시 풀어봐야함

-점화식: s(i)=2*s(i-2)+s(i-1)

점화식은 각 항의 값을 직접 구해서 규칙성을 찾으려했음 

 

-정답 풀이:

• 마지막에 10007로 나누는 거 잊지말기 
• dp 초기값 설정하는데 오류발생(dp=[0 for i in range(n)]이라고 설정해서 되도록이면 끝값으로 크게 설정하기)
• 이것도 n번째 인덱스 값을 출력해야함