수학과의 개발자 도전기

1. 12865번: 평범한 배낭 

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

어려웠던 문제

-정답 풀이: 

• item에는 문제 값 대입(인덱스0에는 물건의 무게가, 인덱스1에는 물건의 가치가 들어있다)
• N[0],K[0]에는 0값을 넣어준다 -> (N+1)x(K+1) 행렬인 dp 생성 

• i번째 물건의 무게가 남은 무게보다 작을때 가치값 변경됨 
• 당연히 i번째 물건의 무게가 오버되면 가방에 넣을 수 없으므로 이전행값과 동일하게된다(else문)
• 점화식: dp[i][j]=max(dp[i-1][j],dp[i-1][j-item[i][0]]+item[i][1]) -> 점화식 아직 이해 안갔음

2. 11054: 가장 긴 바이토닉 부분 수열

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

가장 긴 수열 구하는 문제를 알면 풀  수 있는 문제.

-정답풀이: 

• 증가하는 수열부분

• 감소하는 수열부분
• 끝부분부터 거꾸로 진행하면 감소하는 부분도 결국 증가하는 부분과 같은 풀이를 가지게 된다

3. 1699: 제곱수의 합

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

이것도 어려웠던 문제다

-정답풀이:

• 8번 9번 점화식이 아직 이해가 가지 않는다. 추후로 더 봐야할 것 같다 

1. 9251번: LCS

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

1) 단어 두개 받는 문장을 처음 봐서 공부해야할 것 같다.

2) 그리고 LCS값 저장하는 리스트는 dp로 선언해서 진행하면된다 

3) LCS의 점화식은 다음 페이지에 있음()

4) 추가로 알아야할 것: [[0이 a개 있음 ]0이 b개 있음 ]-> bxa 행렬 생성

-정답풀이:

• sys.stdin.readline().strip().upper()알아두기 

• 위의 4)번에 해당되는 내용. 입력되는 두 글자의 길이가 다를 수 있어서 정확하게 len1,lens2 입력하기 
• i==0, j==0일 때는 dp[i][j]==0이고, 거기에 추가로 글자수가 입력되는 것이므로
• 전체 행렬 길이 == 글자길이+1

• LCS 점화식 

2. 11057번: 오르막수

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

풀이 안 보고 스스로 푼 문제. 1시간 40분 걸림. 

-정답풀이: 

n=int(input())

a=[[1 for _ in range(10)] for _ in range(n)]

for i in range(1,n):
    for j in range(1,10):
        a[i][j]=a[i][j-1]+a[i-1][j]
        
print(sum(a[n-1])%10007)

-풀이 과정:

1. 처음 문제를 읽고 작성한 풀이. 이 방법으로하면 코드가 복잡해지고, 답을 못구해서 포기하고 다른 방법을 찾으려고 했다

2. 첫번째 수열을 뒤집어서 1이 맨 위로 가게했더니 색깔펜으로 칠한 규칙을 발견했다

3. 규칙을 기반으로 nx10 행렬 작성 후 코드로 옮겨서 제출함 

3. 2293번: 동전1

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

:처음 보는 유형. 아직 풀이가 이해 안가서 여러번 봐야할 것 같다 

-정답풀이: 

-풀이 이해:

1. 9461번: 파도반 수열 

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

수열이 1,1,1,2,2,3,4,5,7,9로 진행되는 것에 기반해서 점화식까지 구하는 건 성공함.오늘 풀었던 세문제 중 가장 쉬웠던 문제

-점화식: P(N)= P(N-5)+P(N-1)

-정답풀이 : 

-틀린 풀이1:

• 4번에 i를 j로 바꿔야함(이거때문에 뻘짓함. NameError 조심)

-틀린 풀이2:

• dp에 숫자 모두 입력되고, 거기서 출력하는것이 맞음

2. 14051번: 퇴사 (여러번 반복해서 봐야할 문제)

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

0번째 컬럼부터 생각하고 알고리즘 설정하려고 했는데 이게 아니라 마지막 컬럼을 기준으로 풀어나가야하는 문제 

-정답풀이: 

n=int(input())
T=[]
P=[]
dp=[]

for i in range(n):
    x,y=map(int,input().split())
    T.append(x)
    P.append(y)
    dp.append(y)
    
dp.append(0)#n번째 인덱스에 0대입 

for i in range(n-1,-1,-1):
    if T[i]+i>n:#일이 퇴사후까지 진행되면 다음으로 넘김
        dp[i]=dp[i+1]
    else:
        dp[i]=max(dp[i+1],P[i]+dp[i+T[i]])
print(dp[0])

:여기서 왜 dp[i+T[i]]가 나오는지 이해가 가지 않는다 

3. 9465번: 스티커 

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

이것도 어려웠던 문제 대각선으로 값을 더해야하는 건 알겠는데 어떻게 진행해야하는지 몰랐던 문제. 

-정답풀이:

t=int(input())
for i in range(t):
    s=[]
    n=int(input())
    for k in range(2):
        s.append(list(map(int,input().split())))
    for j in range(1,n):
        if j==1:
            s[0][j]+=s[1][j-1]
            s[1][j]+=s[0][j-1]
        else:
            s[0][j]+= max(s[1][j-1],s[1][j-2])
            s[1][j]+= max(s[0][j-1],s[0][j-2])
    print(max(s[0][n-1],s[1][n-1]))

1. 1010번: 다리놓기

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

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

-정답풀이: 

• 조합 구하는 식 알아두기 

2. 11052번: 카드 구매하기

-문제: https://www.acmicpc.net/problem/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

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

-정답풀이: 

-틀린 풀이: 

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