수학과의 개발자 도전기

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

이전에 풀었던 문제와 같은 패턴의 문제

-정답풀이:

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

가장 긴 수열 갯수 구하는 문제와 같은패턴이라 쉽게 풀었던 문제. 스스로 풀었던 문제

-정답풀이: 

n=int(input())
dp=list(map(int,input().split()))
m=[0]*n
m[0]=dp[0]

for i in range(1,n):
    for j in range(i):
        if dp[i]>dp[j] and m[i]<m[j]:
            m[i]=m[j]
    m[i]+=dp[i]
    
print(max(m))

• 8번라인에 m[i]<m[j]과 9번라인 때문에 여러번 틀렸음.
• 값은 크더라도 그때까지 합이 j가 더 크면 원하는 답을 못함 따라서 m[i]< m[j] 만족하는지 확인해야함
• 9번은 이전 값을 누적해야하므로 필요한 과정 
• 10번은 조건만족하는 수를 더해야하므로 있어야하는 라인이다

-틀린풀이: 

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

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

-정답풀이: 

-풀이 이해: