수학과의 개발자 도전기

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

점화식은 전에 알고 있어서 크게 어려지 않았는데, 맞지막에 답 출력할 때 10007로 나누는 거를 안해서 틀렸다

출력 조건 정확히 기억하기!!

-정답 풀이 

n=int(input())
dp=[0]*1001
dp[1]=1
dp[2]=2
for i in range(3,n+1):
    dp[i]=dp[i-1]+dp[i-2]
print(dp[n]%10007)

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

점화식을 이용해서 풀어야하는 것은 알고 있었지만 1,2,3으로만 숫자 구성해야하는 거를 간과함

그래서 f(1)=1, f(2)=1, f(3)=3으로 생각해서 점화식이 이상하게 나왔음 

근데 1,2,3은 각각 1,2,3으로도 구성 가능하므로 f(1)=1, f(2)=2, f(3)=4 이다 

따라서 점화식은 f(n)=f(n-1)+f(n-2)+f(n-3)

이거를 통해서 만든 풀이는 다음과 같다 

-정답풀이

t=int(input())
for _ in range(t):
    dp=[0]*12
    n=int(input())
    dp[1],dp[2],dp[3]=1,2,4
    if n<=3:
        print(dp[n])
    else:
        for i in range(4,n+1):
            dp[i]=dp[i-1]+dp[i-2]+dp[i-3]
        print(dp[n])

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

-정답 풀이

0을 담는 배열과, 1을 담는 배열을 따로 초기화 한 후 이들끼리 피보나치 수열을 진행하면 된다고 생각했다

f(n)=f(n-1)+f(n-2)

점화식 값을 삽입하는 형태로 했는데, 틀린 답이 나왔다. python tutor를 돌려보니 길이가 22일 때, len(one),len(zero)의 값이 27이 되었으며, 틀린 답을 출력했다. 

length=len(zero)

if length <= n 부분을 입력하지 않아서 틀렸던 것 같은데, 아직 이유를 잘 모르겠다. 

t=int(input())
zero=[1,0,1]
one=[0,1,1]
for _ in range(t):
    n=int(input())
    length=len(zero)
    if length <= n:
        for i in range(length,n+1):
            zero.append(zero[i-2]+zero[i-1])
            one.append(one[i-1]+one[i-2])
        
    print(zero[n],one[n])

-틀린 풀이 

t=int(input())
zero=[1,0]
one=[0,1]
for _ in range(t):
    n=int(input())
    for i in range(2,n+1):
        zero.append(zero[i-2]+zero[i-1])
        one.append(one[i-1]+one[i-2])
        
    print(zero[n],one[n])

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

거의 3번째로 푸는 문제인데, 또 못 풀었다 이번에는 꼭 풀이 다 이해하고, 작성까지 연습하고 가야겠다 

n이라는 숫자는 n-1에서 1을 더하거나, n//2에서 2를 곱하거나, n//3에서 3을 곱한 경우가 있다 

따라서 점화식으로는 dp[n]=min(dp[n//3]+1,dp[n//2]+1,dp[n-1]+1)인데, 이를 그대로 이용하는 것이 아니라 

n이 3의 배수인 경우와 2의 배수인 경우를 나눠서 dp[n-1]+1과 비교해야 한다 

n이 모두 2와 3의 곱으로 이루어진 경우는 없지만, n-1에서 +1이 된 경우는 있기 때문이다. 

따라서 정답풀이를 작성하면 다음과 같다 

for문의 범위가 2부터 시작하는 이유는

1부터 시작한다면 dp[1]==1이고, dp[2]==2가 되므로 틀리기 때문이다. 

문제는 1까지 가는 경우의 수를 말했으므로, dp[1]==0이어야 한다 그래야 dp[2]==1이 된다 

여전히 다 풀지 못했지만, 적어도 풀이가 이해가 가서 조금이라도 발전했다

n=int(input())
dp=[0 for _ in range(n+1)] 

for i in range(2,n+1):
    dp[i]=dp[i-1]+1
    if i%2==0 :
        dp[i]=min(dp[i//2]+1,dp[i])
    if i%3==0 :
        dp[i]=min(dp[i//3]+1,dp[i])
        
print(dp[n])

위의 풀이는 정답인데, 왜 밑에 풀이는 정답이 아닌지 모르겠다 그냥 같은거 대체한 거 아닌가??

n=int(input())
dp=[0 for _ in range(n+1)] 

for i in range(2,n+1):
    dp[i]=dp[i-1]+1
    if i%2==0 :
        dp[i]=min(dp[i//2]+1,dp[i-1]+1) #여기와
    if i%3==0 :
        dp[i]=min(dp[i//3]+1,dp[i-1]+1) #여기만 다르다
        
print(dp[n])