[코딩테스트]#5. 2579번, 11053번, 1932번

1. 2579번: 계단오르기

문제: https://www.acmicpc.net/problem/2579

2579번: 계단 오르기

 

-정답 풀이: 

마지막 계단을 밟아야 하므로 마지막 값인 s[i]을 항상 더해야함 . 상황은 아래처럼 두가지가 있다 

case 1 : 마지막 이전 계단을 밟고 있는 경우

case 2: 마지막 이전 계단을 밟지 않고 있는 경우 

 

-점화식:

 

 

-틀린 풀이: 

 

시작부분부터 올라가는 걸로 풀어서 문제 조건(마지막 계단을 꼭 밟아야한다)을 만족 안 할 수도 있음.

고로 마지막 계단 입장에서 생각해야함-> 역시나 점화식을 생각하는 것이 관건

 

 

 

2. 11053번: 가장 긴 증가하는 부분 수열

문제: https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

 

 

처음들어본 가장 긴 증가하는 수열

여기서는 리스트를 두개 만들어서 수열의 개수를 넣는 것이 관건이었다.

 

-정답 풀이:

:값이 큰 것 중에 a인덱스 값이 작은 수에 한하여 숫자를 누적하고, 이후에 하나씩 증가하는 방식

 

-틀린 풀이:

뭔가 맞는 것 같은데 append를 썼는데 계속 IndexError가 발생했다. 왜인지 생각해봐야할듯

->NOPE. 문제에서는 정보가 하나의 리스트로 다 주어졌기 때문에 반복문에 append하면 안됨. 초기값 잘못 받았음!!(2022.06.02)

 

3. 1932번 : 정수 삼각형 

문제: https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

 

 

-정답 풀이

: 5번까지는 어느정도 작성 했는데  밑부분을 생각하는 것이 어려웠음. 

삼각형 가장 마지막 까지 규칙대로 더했을 때 가장 큰 값을 출력하면됨

i 번째 행렬에서 0번 컬럼와 (i-1)컬럼은 바로 위의 값과 더하면 되므로 아래 if,elif 문과 같이 작성하면 되고,

나머지는 전 행의 대각선 왼쪽,오른쪽 값과의 합 중에 최댓값을 넣으면 된다

-틀린 풀이:

위에서부터 아래로 더해나갔는데 i+1행에서 값을 더하는 것이 어려웠음. 아무튼 이렇게 생각하거나, 작성하면 안된다는 것을 알게됨