백준/ Silver 2 문제 , 백준 파이썬 1182 , 부분수열의 합
Check Point ! ( 해당사항 ✓체크 )
1. 막힘 없이 수월하게 풀린 문제인가?
2. 1시간이내로 풀렸던 문제인가?
3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?
4. 시간을 써도 도무지 풀 수 없는 문제인가?
5. 솔루션을 찾아봤는가?
-------------------------------------------------------------------------------------------
난이도 체감
1. 최상
2. 상
3. 중
4. 하
<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함
<덧붙일 말>
약간 시간 걸린 문제, 백트래킹으로 접근했는데 시간 초과가 나와서 코드를 다 갈아 엎었다.
<문제 출처>
https://www.acmicpc.net/problem/1182
1182번: 부분수열의 합
첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.
www.acmicpc.net
------------------------------------------------------------------------------------------------------------------------------
1) 시간초과
처음에 작성한 코드인데 시간초과가 발생했다.
아무래도 여러 경우들을 다 정렬해가며 비교해야되서 시간이 많이 걸린것 같다.
마지막 출력 부분은 S==0 일때 공집합도 포함되어서 따로 분류해서 출력을 해준것이다.
이후 코드를 갈아엎고 부분수열들을 구해서 합을 비교하는 식으로 계산했다.
함수도 사용하지 않고 이전 코드보다 간결하게 풀이가 가능하였다.
------------------------------------------------------------------------------------------------------------------------------
정답
반응형
'알고리즘 공부 > 백준 - 파이썬' 카테고리의 다른 글
| 백준/ Silver 4 문제 , 백준 파이썬 1049 , 기타줄 (0) | 2022.04.05 |
|---|---|
| 백준/ Silver 5 문제 , 백준 파이썬 2435, 기상청 인턴 신현수 (0) | 2022.04.03 |
| 백준/ Silver 2 문제 , 백준 파이썬 10819 , 차이를 최대로 (0) | 2022.03.29 |
| 백준/ Silver 3 문제 , 백준 파이썬 10211, Maximum Subarray (0) | 2022.03.29 |
| 백준/ Silver 3 문제 , 백준 파이썬 13414 , 수강신청 (0) | 2022.03.26 |