백준/ Silver 1 문제 , 백준 파이썬 11052 , 카드 구매하기
Check Point ! ( 해당사항 ✓체크 )
1. 막힘 없이 수월하게 풀린 문제인가?
2. 1시간이내로 풀렸던 문제인가?
3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?
4. 시간을 써도 도무지 풀 수 없는 문제인가?
5. 솔루션을 찾아봤는가?
-------------------------------------------------------------------------------------------
난이도 체감
1. 최상
2. 상
3. 중
4. 하
<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함
<덧붙일 말>
함수로 풀어내려다가 너무 복잡해져서 좀 더 간략한 풀이를 찾아봤더니 for 중첩문으로 쉽게 풀렸음.
<문제 출처>
https://www.acmicpc.net/problem/11052
11052번: 카드 구매하기
첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)
www.acmicpc.net
------------------------------------------------------------------------------------------------------------------------------
1) 인덱스 맞춰주기
2) 최댓값을 따로 저장
check 리스트에 단계적으로 최댓값을 부여하면서 올라간다.
이렇게 계산하면 장점이 세부적인 연산을 따로 안해줘도 된다는 것이다.
예를 들면 2의 최댓값은 1+1 이나 2 의 숫자중 최댓값을 부여하면 된다.
3으로 올라가면 최댓값은 1+1+1 이나 1+2 , 3 이 세가지를 비교해야하는데
이미 위에서 1+1 와 2 를 비교 했으므로 1+1 의 값이 더 크다면 1+1+1 이 자연스럽게 1+2 보다 크게 될 것이다.
결과적으로 비교할 값은 1+1+1 이랑 3 이 두가지만 비교해서 큰 값을 찾아내면 된다.
이런식으로 계산할 값이 적어져서 연산 횟수가 줄어 든다.
불필요하게
5를
1+1+1+1+1
1+1+1+2
1+2+2
1+1+3
2+3
5
이렇게 여러 경우의 수들로 나누어 일일이 다 비교를 해주지도 않아도 된다.
------------------------------------------------------------------------------------------------------------------------------
정답
'알고리즘 공부 > 백준 - 파이썬' 카테고리의 다른 글
| 백준/ Silver 3 문제 , 백준 파이썬 10947 , 모든 순열 , dfs (0) | 2022.02.02 |
|---|---|
| 백준/ Silver 2 문제 , 백준 파이썬 6603 , 로또 (0) | 2022.02.01 |
| 백준/ Silver 5 문제 , 백준 파이썬 2941 , 크로아티아 알파벳 (0) | 2022.01.29 |
| 백준/ Silver 5 문제 , 백준 파이썬 4673 , 셀프 넘버 (0) | 2022.01.28 |
| 백준/ Silver 2 문제 , 백준 파이썬 15665 , N과 M(11) (0) | 2022.01.28 |