수학과의 개발자 도전기

-문제: 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])

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

이는 주어진 정보를 역순으로 한 뒤에

증가하는 가장 긴 수열의 길이를 구해

전체 길이에서 빼면 답이 나온다 

처음에는 for문 두개가 아니라 한개로 했는데, 이때 틀렸다. 

이유는 0부터 i번째까지 증가하는 수열을 찾아야하는데, for문이 하나면, 국소적으로 i랑 i-1번째랑만 비교하므로 전체적인 수열을 구할 수 없다. 

for문 두개를 이용하면 답이 나온다. 

여기에서 length[i]+=1의 위치가 for j~를 나올 때 수행돼야 정답이 나오는지 궁금했다. 

그래서 두가지 경우에 대해 결과를 도출해봤다

1.

for i in range(n):
    for j in range(i):
        if data[i]>data[j] and length[i]<length[j]: #큰 수가 수열에 포함되지 않는 경우          
            length[i]=length[j] #이전 수열 값 누적
    	    length[i]+=1

이 경우에는 length의 모든 원소가 0인데, 크기 차이가 있어야지 +1 연산이 가능하기때문에 

결국 length의 모든 원소가 0인 상태로 끝난다 (length=[0,0,0,0,0,0,0])

2. 

for i in range(n):
    for j in range(i):
        if data[i]>data[j]: #큰 수가
            if length[i] <length[j]: #수열에 포함되지 않을 경우
                length[i]=length[j] #이전 수열 값 누적
    	length[i]+=1

이 경우는 data[i]> data[j]이 아닌 경우에도 length[i]+=1 연산이 수행된다. 

length = [0,1,2,3,4,5,6]

정답은 인덱스 5의 값이 2여야 하고, 인덱스 6은 4, 인덱스 7은 5여야 한다 

-정답풀이: 

n=int(input())
array=list(map(int,input().split()))
length=[0]*n
data=[0]*n
for i in range(n):
    data[i]=array[n-1-i]
    
for i in range(n):
    for j in range(i):
        if data[i]>data[j]: #큰 수가
            if length[i] <length[j]: #수열에 포함되지 않을 경우
                length[i]=length[j] #이전 수열 값 누적
    length[i]+=1
            
print(n-max(length))

-틀린 풀이

n=int(input())
array=list(map(int,input().split()))
length=[0]*n
data=[0]*n
for i in range(n):
    data[i]=array[n-1-i]
    
for i in range(1,n):
    if data[i]>data[i-1]:
        if length[i]<length[i-1]:
            length[i]=length[i-1]+1
            
print(n-max(length))

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

이전에 풀었던 풀이는 여기에 있다 

여기에서 t[i]+i를 왜 하는지 모르겠다고 되어있는데, 이는 간단하다. i번째 날에 상담을 했다면 상담을 끝난 날부터 다른 상담을 할 수 있으므로, 다음 상담을 할 수 있는 날이 i+t[i]인 것이다. 이때의 상담료를 보면된다 

-정답 풀이: 

풀이 방법으로 0번부터 차례로 상담가능한 날짜들을 기준으로 상담료를 더하는 것으로 생각했다. 

그리고 index+data[index][0]인 날을 기준으로 또 상담을 진행하는 것이라고 생각했다. 

여기서 고민되었던 게, i+t[i]일부터 상담을 할 수 있다는 것이지, 이날에 꼭 상담을 해야하는 것은 아니다. 

이 이후에 날에 기간내에 끝낼 수 있고, 더 많은 돈을 벌 수 있는 날이 있을 수 있기에 순차적으로 하기엔 어렵다고 생각했다. 

그래서 잘 풀리지 않아서 답지를 봤다 

일단 순서는 끝 인덱스부터 시작해야 한다.(for i in range(n-1,-1,1))

인덱스가 거꾸로 가므로 max_value는 dp[i+1]을 의미. 

n=int(input())
t=[]
p=[]
dp=[0]*(n+1)
max_value=0

for _ in range(n):
    x,y=map(int,input().split())
    t.append(x)
    p.append(y)
    
for i in range(n-1,-1,-1):
    time=t[i]+i
    if time <= n:
        dp[i]=max(p[i]+dp[time],max_value)
        max_value=dp[i]        
    else:
        dp[i]=max_value
print(max_value)