티스토리 뷰
이번엔 사탕 문제 두개를 풀었다. 사수아탕이랑 사수빈탕인데 비슷해 보이는데 난이도 차이가 심각하다.
14585번: 사수빈탕
수빈이는 좌표평면 위에 앉아있다. "나는 좌표평면이 너무 좋아!!" 라고 수빈이가 말했다. 좌표평면에는 N개의 사탕바구니가 있고, 각 사탕 바구니에는 M개의 사탕이 있다. 각 사탕 바구니는 (x1, y
www.acmicpc.net
사수빈탕은 쉽다. 단순 2차원dp로 풀면 되는데 함정은 M 최대가 100만이라 사탕이 (0, 0) 근처에 몰려있으면 int로는 부족할 수 있다는 점. 이거 못알아채서 두번이나 틀렸다.
2419번: 사수아탕
첫째 줄에 n과 m이 주어진다. 둘째 줄부터 n개의 줄에 사탕 바구니의 위치 xi가 주어진다. (0 ≤ n ≤ 300, 1 ≤ m ≤ 1,000,000, -10,000 ≤ xi ≤ 10,000) 사탕 바구니의 위치는 중복되지 않는다.
www.acmicpc.net
문제는 사수아탕이다. 뭔가 위에 사수빈탕은 2차원인데 얘는 1차원이라 더 쉬워보이지만, 아이디어랑 풀이 방법이 완전히 다르다. 왜냐면 경우에 따라서 왔던 길을 다시 가야 최대일 수 있기 때문이다. 문제 예제만 보더라도 1로 갔다가 -3으로 가는게 최대이다. 같은 이유로 그리디로도 정답을 구할 수 없다.
그래서 문제를 보는 방향을 바꿔야 한다. 우선 몇 개의 바구니를 찾아갈지 정한다. B개의 바구니를 방문한다고 하면 0 < B < N이고, 각각의 경우에 대해서 계산을 할 것이다. 만약 b개의 바구니를 지날 때가 정답이라면 b보다 큰 B에 대해서는 정답이 나오지 않거나 같을 것이다. 그럼 b를 찾고 b개의 바구니를 지나는 부분문제에 대해서 이동거리의 최솟값을 구하면 된다. 그럼 시간복잡도가 $O(N^3)$인데 N < 300이므로 1초안에 충분히 돌아가 이게 정해다. int 오버플로우도 생각해야 된다.
그런데도 시간초과가 나서 확인해 봤는데 나 같은 경우는 매 경우마다 새로 dp 벡터를 만들었는데 이때 dp[301][301][2]로 하니 시간초과가 나고 dp[2][301][301]로 하니 통과됐다(...)
https://stackoverflow.com/questions/2275076/is-stdvector-copying-the-objects-with-a-push-back
Is std::vector copying the objects with a push_back?
After a lot of investigations with valgrind, I've made the conclusion that std::vector makes a copy of an object you want to push_back. Is that really true ? A vector cannot keep a reference or a
stackoverflow.com
이걸 보면 알 수 있는데 초기화할 때 벡터를 담아 초기화(기본 사이즈대로 정적 할당)하는 식으로 코드를 짰는데 dp[301][301][2]는 vector<vector<int>>[301][2]를 301개 복사해야 되는 반면 dp[2][301][301]은 dp[301][301] 두번만 더하면 된다. 이게 문제가 아닐까 싶다. 뭐지 쓰고보니까 똑같은거 같은데
using ll = long long;
vector<vector<vector<ll>>> dp(2, vector<vector<ll>>(301, vector<ll>(301, -1)));
2315번: 가로등 끄기
첫째 줄에는 2개의 정수 N(1 ≤ N ≤ 1,000), M 이 있다. 첫 번째 정수 N은 가로등의 개수를 나타내는 정수이고, 두 번째 정수 M은 마징가 처음에 위치하는 가로등 번호이다. 다음 N 개의 줄에는 각 가
www.acmicpc.net
얘도 사탕문제랑 비슷하다. 반대로 시간이 지날때마다 점점 비용이 늘어나니까 빠르게 모든 가로등을 다 꺼야 되고, 사수아탕에서 M이 무한대인 상황하고 같다면 같다. 약간 다른점은 사탕 바구니마다 녹는 속도가 다르다는 점. 그리고 결과적으로 모든 가로등에 방문해야 되기 때문에 사수아탕처럼 방문할 개수를 특정지을 필요는 없었다.
'코딩일지' 카테고리의 다른 글
| 9월 일지 (0) | 2023.09.30 |
|---|---|
| 백준 그리디 일지 (3) (0) | 2023.04.29 |
| 백준 그리디 일지 (2) - 순열 사이클 분할 (0) | 2023.04.05 |
| 백준 그리디 일지 (1) (1) | 2023.03.31 |
| 백준 DP 일지 (1) (0) | 2023.03.29 |