[코딩테스트]#10. 백준 9251번,11057번, 2293번

1. 9251번: LCS

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

9251번: LCS

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

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

2293번: 동전 1

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

 

-정답풀이: 

 

 

-풀이 이해: