https://www.acmicpc.net/problem/2228 [초기 접근 방법] - 문제 이해 잘못 (2번 조건을 무시하고 '배열 구간 나누기'로 풀었다.) 그래도 이 때 문제 풀이를 적자면, 골드3 문제인데, dp[]가 1차원 배열이라니 뭔가 이상했어... [생각] 틀리고 '반례가 있을까?' 질문 게시판을 찾아보다가 접근이 아예 잘못된 것 같아서 구글링을 했다. 1. dp[i][j] : i개의 배열로, j개의 구간을 선택했을 때 구간합 최댓값 - 이 때 주의할 점은 배열을 이루는 수에는 음수도 있기에, -float('inf')로 초기화한다. 2. 점화식 1) 현재 구간을 유지하면서, i번째 값을 포함시키지 않았을 경우 dp[i][j] = max(dp[i][j], dp[i-1][j]) 2) 새로운 ..

[초기 접근 방법] 1. dp[i] : 합이 i가 되는 제곱수들의 최소 갯수 2. 점화식 dp[n] = min(dp[n], dp[n-제곱수] + 1) → 제곱수가 n보다 작을 때까지 비교 [생각] 문제에서 원하는 "합이 i가 되는 제곱수들의 최소 갯수"를 dp로 정의하고 풀면 되는 문제였어서, 쉽게 풀었던 것 같다. 아.. 시간 제한이 0.5초 이길래 시간초과가 나올까 봐 상수 시간복잡도까지 구했었다 [코드] # 풀이 시간 : 15분 # 시간복잡도 : O(N*sqrt(N)) → 1100만? # 공간복잡도 : O(n^2) # 참고 : - # 점화식을 세우자.. ㅎㅎ import math import sys input = sys.stdin.readline N = int(input()) # dp[i] : 합이..

https://www.acmicpc.net/problem/5557 [초기 접근 방법(o)] 1. 먼저 dp 메모제이션 할 배열을 정의하자 2. dp[i][j] : i번째 수까지 보았을 때, 수식을 만들어서 j가 나오는 경우의 수 - 0

[초기 접근 방법(x)] 1. 직행 다리가 감당이 가능하면, 가능한 중량을 올린다. 2. 직행 다리가 감당이 불가능하면, 경유 다리를 탐색하자 1) 경유 다리가 감당이 불가능한 경우, 가능한 중량을 내린다. 2) 경유 다리가 감당이 가능한 경우, 가능한 중량을 올린다. [생각] 위와 같이 접근을 하게 되면 감당 가능한 무게가 작은, 쓸데없는 다리가 있을 경우에 목적지까지 갈 수 있음에도 판단하지 못한다. - search 함수를 다음과 같이 작성하면 틀린다. 왜?? def search(start, end): while start < end: mid = (start + end) // 2 # 다리들이 현재 mid 무게를 감당 가능하면, 더 중량을 올려도 됨 if bfs(mid): start = mid + 1 ..

https://www.acmicpc.net/problem/17626 [초기 접근 방법] - dp[n] = min(dp[n], dp[n-제곱수] + 1 (n >= 제곱수) [생각] dp[n]를 문제에서 정의해줘서 쉬운 문제였다. 점화식 또한 쉽게 생각할 수 있는 로직이여서 금방 풀었던 것 같다.. 아.. 입력 범위 끝인 '50000'을 넣었는데 1-2초? 정도 걸리길래 시간초과 뜨나 해서 시간복잡도 상수 계산까지 했던.. 에피소드가 있다;; [코드] # 풀이 시간 : 15분 # 시간복잡도 : O(N*sqrt(N)) → 1100만? # 공간복잡도 : O(n) # 참고 : - import math import sys input = sys.stdin.readline N = int(input()) # dp[i] ..

https://www.acmicpc.net/problem/1300[초기 접근 방법(X)]1. N^2의 [i][j] 값을 모두 lst에 넣으려면 시간복잡도가 이미 O(N^2)으로 시간초과이다.2. 그러면? 시간복잡도를 줄일 수 있는 방법은, 처음부터 [i][j] 값을 lst에 넣지 않는 것3. 그런 [i][j] 값을 전부 넣지않고, 어떤 값을 lst에 넣어야 하는가? 에서 시작했다. 대각선을 기준으로 중앙값이 가장 크므로,이분탐색을 하여 몇번째 대각선인지 찾고 남은 인덱스만큼 이동탐색하면 K번째 수를 찾으려고 했다.   [생각]위 방식대로 로직을 짜고 풀었지만 결과는 "틀렸습니다"저 로직을 생각하는데도 시간을 많이 썼던 문제라서, 미련없이 정답 코드를 참고했다...일단 K번째 수는 '1행의 원소들'이 존재..