백준/ Silver 2 문제 , 백준 파이썬 11055 , 가장 큰 증가 부분 수열
Check Point ! ( 해당사항 ✓체크 )
1. 막힘 없이 수월하게 풀린 문제인가?
2. 1시간이내로 풀렸던 문제인가?
3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?
4. 시간을 써도 도무지 풀 수 없는 문제인가?
5. 솔루션을 찾아봤는가?
-------------------------------------------------------------------------------------------
난이도 체감
1. 최상
2. 상
3. 중
4. 하
<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함
<덧붙일 말>
11053 문제 풀고나서 비슷하겠지하고 덤볐다가 대가리 깨졌다.... 진짜 어렵다
내가 제일 어렵다고 느끼는게 예시는 출력 되는데 반례를 못찾을때이다.
진짜 뭐가 잘못된건지 바로 알 수 가없어서 오랜 고뇌와 싸워야한다.
<문제 출처>
https://www.acmicpc.net/problem/11055
11055번: 가장 큰 증가 부분 수열
수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수
www.acmicpc.net
------------------------------------------------------------------------------------------------------------------------------
이 문제에서 가장 헷갈리던 것이 예제를 실행했을때
1 100 2 50 60 3 5 6 7 8
1 100 2 50 60 3 5 6 7 8
위 처럼 이어야 하는지 아래 처럼이어야 하는지였다.
결론적으로 말하자면 위가 맞다.
하지만 이게 헷갈려서 밑에로 코드를 짰다가 틀리고 위로도 코드로 짜서 답은 나오는데 틀리고 아주 틀림의 연속~
어제 오늘 푼 문제들중에서 코드는 가장 간단하지만 for 문 내를 생각해내는게 가장 어려웠다.
도무지 생각이 안나 여러 블로그님들의 풀이를 참고했지만, 이해되게 설명해주시는 분은 없었다...
내가 이해한대로 한번 설명을 해보려 한다.
우선 입력을 받는건 간단하니 넘어가고
dp[0]=A[0]
이 코드부터 보자.
이전 dp 문제에선 선언해주지 않았던 코드이다.
A[0]을 dp[0]에 넣어주고 시작하는데
이유는
for i in range(1, N):
for j in range(i):
이 코드 때문이다.
초반에 i 를 0 부터시작하게되면 안에 있는 for 문은 0을 전달받아 루프를 돌지 않는다.
그래서 dp[0] 은 0값을 가지고 진행되므로 결과값이 달라진다.
그러므로 애초에 시작부텅 dp[0] 만 따로 선언을 해주고 첫번째 for문을 1부터 시작해주는 것이다.
for i in range(N):
for j in range(i):
if A[i] > A[j]:
dp[i]=max(dp[i],A[i]+dp[j])
else:
dp[i]=max(dp[i],A[i])
if i==0:
dp[0]=A[0]
물론 이렇게 밖에 안쓰고 안에 써주는 방법도 있다.
이후 for 문 안을 살펴보자.
if A[i] > A[j]:
dp[i]=max(dp[i],A[i]+dp[j])
else:
dp[i]=max(dp[i],A[i])
나는 이 코드가 가장 어려웠다.
if 문을 A[i] > A[j] 로 설정해주는 건 오케이 알겠으.
근데 dp[i]=max(dp[i],A[i]+dp[j])
이 코드를 어떻게 생각해내느냐가 관건이였다.
i가 1이고 100 을 만났을때
dp[1]=max(dp[1], 100+dp[0]) 여기서 dp[0]은 1
그래서 dp[1] 에는 101 이 들어간다.
이게 코드를 보고 이해하는건 쉬운데... 이 코드를 생각해내서 작성하는건 천지차이다.
(물론 나만 어려울 수도 있다... 아직 내 수준이 이정도라는것. 열심히하자)
내가 헷갈린건 j를 어떻게 사용해야 할까 였다. j는 루프를 계속 도는데 dp 에다가 값을 부여하면 값이 생각보다 더 커졌다.
이때 사용하는게 max이다. max로 나올 수 있는 최댓값만 할당한다.
dp[j] 값을 계속확인하면서 더 큰 값이 있는지 확인해주고 값을 할당한다.
좀 더 이해되게 예시를 한번 살펴보자.
1 100 2 50 60 을 지나 3을 만났을때 루프를 확인 해보자.
이때 까지 dp는 [1, 101, 3, 53, 113, 0, 0, 0, 0, 0] 이다.
i=5 인 상태,
dp[5]=0, A[5]=3
j 는 4까지 총 5번의 루프를 돈다.
------------------------------------------------------------------------------------------------------------------------------
j=0
if 문에 속한다.
dp[5]=max(dp[5], A[5]+dp[0])
dp[5] = max(0, 3+1) = 4
------------------------------------------------------------------------------------------------------------------------------
j=1
else 문에 속한다.
dp[5]=max(dp[5], A[5])
dp[5] = max(4, 3) = 4
------------------------------------------------------------------------------------------------------------------------------
j=2
if 문에 속한다.
dp[5]=max(dp[5], A[5]+dp[2])
dp[5] = max(4, 3+3) = 6
------------------------------------------------------------------------------------------------------------------------------
j=3
else 문에 속한다.
dp[5]=max(dp[5], A[5])
dp[5] = max(6, 3) = 6
------------------------------------------------------------------------------------------------------------------------------
j=4
else 문에 속한다.
dp[5]=max(dp[5], A[5])
dp[5] = max(6, 3) = 6
-> 여기까지해서 dp[5]는 최종값 6을 가진다는 것을 알 수있다.
순서를 차근차근 확인해가면 알 수 있겠지만
if 문에서만 dp 값이 변한다.
반대로 else 문은 증가순열이 진행되는 사이의 구간으로 값이 변해서는 안된다.
이 if , else문을 통해 증가 순열인 구간들을 찾아내고 값에 변화를 주는 것이 이 문제의 핵심이다.
이런 식의 구조로 dp 값이 매겨진다는 것을 이해하고 다시 코드를 보면 이제 이해가 더 잘 될거다.
------------------------------------------------------------------------------------------------------------------------------
정답
import sys
input=sys.stdin.readline
N=int(input())
A=list(map(int,input().split()))
dp=[0 for i in range(N)]
dp[0]=A[0]
for i in range(1,N):
for j in range(i):
if A[i] > A[j]:
dp[i]=max(dp[i],A[i]+dp[j])
else:
dp[i]=max(dp[i],A[i])
print(max(dp))
'알고리즘 공부 > 백준 - 파이썬' 카테고리의 다른 글
| 백준/ Bronze 3 문제 , 백준 파이썬 2490 , 윷놀이 (0) | 2022.02.04 |
|---|---|
| 백준/ Silver 2 문제 , 백준 파이썬 11722, 가장 긴 감소하는 부분 수열 (0) | 2022.02.04 |
| 백준/ Silver 2 문제 , 백준 파이썬 11053 , 가장 긴 증가하는 부분 수열 (0) | 2022.02.04 |
| 백준/ Gold 5 문제 , 백준 파이썬 2110 , 공유기 설치 (0) | 2022.02.04 |
| 백준/ Silver 3 문제 , 백준 파이썬 2512 , 예산 (0) | 2022.02.03 |