러~프하게 생각하면 2^N개정도의 경우가 나오고 N은 최대 1000까지 주어지니 이 방법은 못 쓴다.
2. DP로 접근
k번째 열까지 채우는 것은
1) k - 2번째 열까지 채우고 세로블록 두 개 연달아 놓거나 가로블록 찍찍 놓거나
2) k - 1번째 열까지 채우고 세로블록 하나 놓거나
이 방법이다.
나는 여기서 k - 2번째 열까지 채우고 세로블록 두 개를 연달아 놓는 것과 k - 1번째 열까지 채우고 세로블록을 하나 놓는 것은 중복되는 것이 있으므로 그 부분을 처리하기 위해 공을 들였는데, 다 풀고 보니 예외처리할 필요가 없었다.
k - 2번째 열까지 채우고 세로블록을 두 개 연달아 놓는 행위가 k - 1번째 열까지 채우고 세로블록 하나 놓는 행위에 포함되기 때문.
k - 2번째 열까지 채우고 세로블록을 두 개 놓는 것을 동시에 놓는 게 아니라 하나하나 놓는다고 해보면, k - 2번째 열까지 채우고 세로블록을 하나 낳고 그 다음에 하나를 마저 놓는 것이지만 처음에 하나를 놓는 과정에서 이미 k - 1번째 열까지 채운 것이 된다는 것이다.
즉 k - 2번재 열까지 채우고 k번째 열까지 채우는 과정은 가로블록을 찍찍 놓는것만 생각하면 되는 것이었다.
일단 아쉬운 대로 내 풀이 공유..
N = int(input())
MOD = 10007
# dp[x][0] : x번째 열까지 채우는데 마지막이 세로로 끝나는 경우
# dp[x][1] : x번째 열까지 채우는데 마지막이 가로로 끝나는 경우
dp = [[0, 0], [1, 0], [1, 1], [2, 1]]
for i in range(4, 1001):
dp.append(
[(sum(dp[i - 2]) + dp[i - 1][1]) % MOD, sum(dp[i - 2]) % MOD]
)
print(sum(dp[N]) % MOD)
더 나은 풀이
N = int(input())
MOD = 10007
dp = [0, 1, 2, 3]
for i in range(4, N + 1):
dp.append((dp[i - 2] + dp[i - 1]) % MOD)
print(dp[N])
느낀점
일단 이런 DP문제를 점화식을 세우는 과정에서 앗? 중복되니까 예외처리할 부분이 있는데? 라고 생각되는 부분들이 있다. k - 2번째와 k - 1번째에 어떤 연산?을 해주어 k번째를 구하는 경우, k - 2번째에서 구하는 것과 k - 1번째에서 구하는 것들이 새로 중복되는 게 있는 거 같은데? 하는. 그러나 k - 2번째에서 특정 연산을 하는 것을 유심히 보며 중간에 k - 1번째가 '되는' 부분이 있는지 봐야할 것이다. 그렇다면 그 부분을 빼고 생각하면 중복처리 땜에 머리 굴릴 필요가 없어지니까. 애시당초 k - 2번째와 k - 1번째에 서로 다른 종류의 연산을 가미해 중복될 일이 없도록 처음부터 생각하는 것도 방법일 듯하다.
그리고 굳이 처음부터 어떤 관계가 있을까 하며 뇌피셜로 점화식 세울라 하지 말고, 일단 2번째일땐 이 만큼의 가짓수, 3번째일땐 이만큼의 가짓수, 4번째일땐 이만큼의 가짓수..하면서 쭉 쓰다가 점화식 관계를 발견하는 것도 하나의 방법일 듯하다. 하나의 틀에 박히지 말자.
어떤 도시들에서 기름을 넣을 건지만 정하면 전체 비용이 정해진다. 첫 번째 도시에선 무조건 기름을 넣어야 하므로, 첫 번째 도시 빼고는 기름을 아예 안 넣을 수도 있다(즉 첫 번째 도시에서 마지막 도시로 갈 수 있을 만큼의 기름을 빵빵하게 넣고 가는 경우에 해당)
이는 첫 도시에서 시작해서 그 다음 도시를 선택할지 안 할건지, 그 다음 도시 역시 선택할지 안 할건지,...각 도시에 대해 두 개의 선택지가 있는 것으로, 이 경우 전체 2^(n-2)개의 방법이 나온다. 이 방법 중 최소비용이 나오는 걸 고르면 됨. 그러나 n은 문제에서 10만까지 주어지므로 이 방법으론 시간 내에 풀 수 없다는 결론
2. 부분문제로 쪼개기 가능?
가능. 마지막 도시로 가는 것은
N - 1번째 도시까지 오고, N-1번째에서 기름 넣고 N번째 도시로 한 번에 가는 경우
N - 2번째 도시까지 오고, N-2번째에서 기름 넣고 N번째 도시로 한 번에 가는 경우
N - 3번째 도시까지 오고, N-3번째에서 기름 넣고 N번째 도시로 한 번에 가는 경우
...
중에서 min값을 찾으면 됨. N - 1번째 도시까지 오는 부분문제, N - 2번째 도시까지 오는 부분문제들이 생기는 것이다.
3. 중복되는 구조 있음? 있으면 DP로 일단 가능할텐데
있음. N - 1번째 도시로 오는 부분문제도 쪼개면 N - 2번째 도시로 오는 경우 등을 구해야 하는데 이것들이 중복되는 것을 관찰가능.
그러나 DP로 풀기엔 애매한게, 이러면 시간복잡도가 O(n^2)정도가 걸리는데 n이 10만까지주어지니까 시간복잡도가 너무 크다. 다른 방법을 모색해야 함.
3. 그리디 의심
문제를 그대로 이해하면 k번째 도시에서 기름을 채우고 채운만큼 갈 수 있다. 그대~로 생각한다면 "나는 지금 이 도시에서 기름을 얼마나 채우고 가야 하는가?"로 생각하게 돼서 조금 시간이 걸렸다. 그러나 이 틀에서 벗어나서, 후불로 요금을 지불한다 생각해보자. 각 도시를 거치면서 그 도시에서 파는 기름을 살 때만 내가 이전에 쓰던 기름값을 낸다고 생각하자는 것이다. 즉 첫 도시에서 시작해(즉 첫 도시에서 기름을 사서) 두 번째 도시에 가면 두 번째 도시에서 파는 기름과 내가 지금 들고 있는 기름(첫 도시에서 산 기름) 중 어떤 기름을 쓸 건지를 선택할 수 있게 된다. 여기서 두 번째 도시에서 파는 기름을 쓰기로 했다면 그 도시까지 오는데 사용된 기름값을 그 때 낸다! 이렇게 되면 내가 지금 들고 있는 기름과 새로 방문한 도시에서 파는 기름 중 더 싼 기름만 선택해서 나가면 된다.
4. 코드
import sys
input = sys.stdin.readline
N = int(input())
length = list(map(int, input().split()))
cost = list(map(int, input().split()))
ans = cost[0] * length[0]
now_cost = cost[0]
for i in range(1, N - 1):
new_cost = cost[i]
now_cost = min(now_cost, cost[i])
ans += now_cost * length[i]
print(ans)
5. 정당성 검증(그리디니까)
상식적으로 당연히 그 때 그 때 더 싼 기름을 사는게 제일 좋다. 굳이 엄밀한 증명이 필요없다고 생각됨.그래도 공부차원에서 귀류법을 사용해 정당성을 검증하자면
가정 : 매 번 가장 싼 기름을 선택해나가는게 답이다.
??? : 아니던데? ㅎㅎ
반박 :
1) 생각할 필요도 없다. 가장 싼 거 선택해나가면 그게 제일 싸잖아.
2) 그래 너 말이 맞다고 해보자.
그럼 최적해 집합 O = {o1, o2, o3, ..., ok, ..., o(n-1)}이 있고
가장 싼 기름을 선택한 집합 G = {g1, g2, g3, ..., gk, ..., g(n-1)}이 있어.
이 집합들이 합이 전체비용이겠지? 그럼 이 두 집합이 다른 집합이니까 1항부터 k항까지의 부분합이 달라지는 k가 어디엔가 존재하겠지. 그러나 생각할 수 있는 건 gk ~ g(n-1)의 합이 ok ~ o(n-1)보다 작다는 거야. 왜냐 G는 매번 가장 싼 기름을 선택한거니까!
이제 새 집합 N = {o1, o2, o3, ..., gk, ..., g(n-1)}을 만들었다고 해보자. O에서 k번째 항부터를 G의 항으로 바꾼거야. 근데 gk ~ g(n-1)까지의 합 < ok ~ o(n-1)까지의 합이니까 N의 전체합은 O보다 작겠지? 근데 O는 최적해니까 지보다 작은 전체합을 가지는 집합이 있으면 안되잖아? 이거 모순이네?
그래서 내 말이 맞아. 즉 매번 가장 싼 기름을 선택해나가야 한다는 거지.
느낀점
결국 그리디는 선택하는 과정이 있고, 그 과정에서 가장 작은/가장 큰 .. 뭐 이런 선택을 한다. 그러나 이 '선택'은 잘 보이지 않을 때가 있다. 이 문제도 단순하게 "계속 대체 지금 도시에서 얼마나 기름을 채워야 하지? 가장 많이 채워야 하나(?)"식으로 생각했다면 계속 헤멨을 것이다. 그러나 그리디가 의심될 때는 가장 작은 값 또는 가장 큰 값 이런 식으로 선택할 수 있게끔 생각을 전환할 필요가 있다. 브루트 포스로 풀 수 없다는 생각이 들고 DP로 풀기도 애매해서 그리디가 의심된다면 가장 ~~한 선택을 쉽게 할 수 있게끔 생각을 전환할 필요가 있다는 점을 알고 가자.
# 각 조별로 반티를 만드는데, 그 조에서 가장 큰 인원의 키 - 가장 작은 인원의 키만큼 돈이 든다
# 조원이 한명이면 드는 돈은 0원
# k개의 조를 만들어야 할 때 생길 수 있는 전체반티비용 중 최소는?
#1. 무식한 방법으로 접근 (브루트포스)
N개의 인원들을 K개의 조로 나누는 모든 경우를 조사해서 그 중 최소비용이 드는 애를 찾으면 될 것이다.
N개의 인원을 K개의 조로 나누는 경우는 (N-1)C(K-1)개이며, 러프하게 생각하면 (N - 1)!정도가 드는 것이니 이 방법으론 시간 내에 통과할 수 없을 거라 생각된다..
#2. 부분문제로 쪼갤 수 있는지 확인 -> DP or 그리디를 의심한다
마지막 조 인원이 1명일 때, 마지막 조에서 발생하는 비용 + 남은 N-1명을 K-1개 조로 나눌 때 드는 최소비용
마지막 조 인원이 2명일 때, 마지막 조에서 발생하는 비용 + 남은 N-2명을 K-1개 조로 나눌 때 드는 최소비용
마지막 조 인원이 3명일 때, 마지막 조에서 발생하는 비용 + 남은 N-3명을 K-1개 조로 나눌 때 드는 최소비용
이 중 최소값이 정답이 될 것이며, 형광펜으로 칠해진 부분이 부분문제.
#3. 혹시 저 부분문제들이 중복되는가? -> 그러면 DP로 풀 수 있을 것이다.
중복된다. f(N, K)가 N명을 K개의 조로 쪼갤 때 발생하는 최소비용이라 하면
f(N, K)를 구하기 위해선 f(N-1, K-1), f(N-2, K-1), f(N-3, K-1)...를 구해야 한다. (바로 위 #2에서 부분문제 쪼개는 부분 참고)
여기서 f(N-1, K-1)을 구하기 위해선 f(N-2, K-2), f(N-3, K-2), f(N-4, K-2), f(N-5, K-2)...를 구해야 하는데
f(N-2, K-1)을 구하기 위해선 f(N-3, K-2), f(N-4, K-2), f(N-5, K-2)...를 구해야 하고
f(N-3, K-1)을 구하기 위해선 f(N-4, K-2), f(N-5, K-2)...를 구해야 한다.
이 구조에서 중복되는 걸 관찰가능.
표로 중복되는 것을 관찰하면 다음과 같다.
#4. 그러나 맞닥뜨린 문제점 - 메모리 이슈 및 시간 이슈
DP로 그럼 잘 풀수 있겠거니 했지만..몇 가지 문제점이 생겼다. 첫 번째는 메모리 제한 이슈. 위 표와 같은 dp테이블을 만들려고 했는데, 그러려면 N * K사이즈만큼의 배열이 만들어지는데 문제는 N과 K의 최대치가 30만이라 30만*30만 = 900억이라는 경이로운 사이즈의 배열이 만들어진다. 그러나 이 문제의 메모리제한은 512MB로...안된다 암튼
또 하나의 문제점 = 시간복잡도. 위 방법으로 하게 될 경우 러프하게 생각하면 O(N^2)정도의 시간복잡도가 드는데, 이게 이 문제의 시간제한인 1초 내에 되리라는 생각이 들지 않는다.
#5. 그리디를 의심해보자
우선 그리디로 해도 괜찮은 문제인지 봤다. 그러나 여기서부터 꼬이기 시작..ㅋㅋㅋㅋㅋ
일단 난 #2에서 세웠던 부분문제에 얽매여 있었기 때문에..그리디로 한다면 처음부터 2명씩 모아간다던가 이런 식으로 생각했다.
일단 그리디 속성?이 현재 내리는 선택이 이후의 선택이 영향을 주지 않는다는 것 즉 내가 지금 2명 모았다고 다음 번 조는 두 명 못 모으나? 그런 건 아니다. ㅇㅋ
지금의 선택 자체로 부분문제가 되는가? 이것도 맞고그리디로 풀 수 있는 문제같긴 한데. 어떤 기준으로 조를 만들어 나가야 하는가라는 문제에 봉착했다. 그리디는 가장 ~~한대로 선택해 나가는 것인데, 키 순서로 이미 서있는 아가들을 어떤 기준으로 모아 나가야 하는가..?
#6. 결국 인터넷으로 서치해봤다
일단 정답은 인접한 애들끼리의 차이값을 계산한 후 이 값들을 정렬하고, N - K개 만큼의 가장 큰 값들을 빼고 남은 값들을 합치면 정답이라고 했다. 나도 풀다가 중간에 인접한 애들끼리의 차이값을 이용하는건가 하고 봤지만,, 암튼 이렇게 하면 됐던 거라고? 라는 생각이 들면서, "그래서 이게 왜 답이 되는데"라는 생각도 들었다.
이게 왜 답이 되는지는 좀만 생각해보면 나올 수 있었다. 키 순서대로 서 있는 애들이 각자 손을 잡고 있다고 해보자. 즉 나는 애 앞에 서있는 애와 바로 뒤에 서있는 애와 손을 잡은 상황. 그리고 각 손에는 우리의 키 차이 만큼의 값을 가진다고 해보자.
여기서 가장 큰 차이를 내는 6이란 아가와 10이란 아가를 보자. 서로의 차이는 4로, 이 두 녀석이 한 조에 같이 있다면 그 조의 반티값은 최소 4이상이란 말이다. 즉 일단 우리는 최소비용을 맞추고 싶으니, 이 두 녀석은 같은 조로 넣으면 안된다! 즉 6과 10이 서로 손을 슬며시 놓는다고 생각해보자. 그리고 손을 잡은 애들끼리 조를 만든다고 하면? 1,3,5,6이 한 조고 10이 한 조로 총 두 개의 조가 만들어진다. 즉, x개의 값을 고르고 그 값들을 가지는 손들을 놓는다고 하면, x + 1개의 조가 만들어진다.
#7. 이렇게 하면 답이 되는 이유
키 순서대로 선 아가들이 있고, 인접한 애들의 차이를 담은 배열이 있을 때, 그 배열의 sum값이 그 조의 반티비용이기 때문이다. 1, 3, 5가 한 조일때 이 조의 반티값은 5 - 1 = 4로 계산할 수도 있지만 1과 3의 차이에 3과 5의 차이를 더한 값과도 같다. 즉 인접한 값의 차이끼리의 합과 그 조에서 최대값 - 최소값은 같다는 것.
또한 앞서 말했듯 그 배열에서 어떠한 값을 뺀다 즉 손을 놓는다는 것은 두 개의 배열로 분리하는 것이라 할 수 있는데, 당연히 이때 제일 큰 값을 빼는 게 좋다. 따라서 K - 1개의 가장 큰 값들을 빼주면 남은 값들의 합이 정답이 된다..
#8. 느낀점
막막하다. 남들은 쉽게 푸는 문제를 내가 나 혼자 어렵게 접근해서 풀려고 한다는 느낌도 든다. 그리디는 창의력이 중요하다는데 내가 창의력이 없이 정해진 루틴대로만 접근하려고 하는 느낌도 든다. 풀이를 보고 나니 아 이렇게 하면 될 수 밖에 없구나라는 생각은 들지만 나 스스로가 그 생각을 떠올릴 수 있을까?라는 생각도 든다.
앞으로 어떻게 문제를 풀어볼지에 대한 고민을 해본다. 내가 지금 하는 방식은 일단 브루트포스로 할 수 있을지 어림짐작해보고, 안되면 DP나 그리디로 풀 수 있는지 보기 위해 1. 부분문제로 쪼갤 수 있는지 보고 2. 중복되는 게 있는지 본다. 아직 나에겐 이 문제가 dp일지 그리디일지 확 알 수 있는 정도의 경험이 없기 때문..근데 이렇게 접근을 해가는게 맞나 싶다. 경험이 충분히 쌓여야지 이 문제는 뭘로 접근해야겠다! 라는 감이 생길 거라는 생각이 들지만, 애시 당초에 이렇게 정해진 방식으로 접근해서 푸는 이런 딱딱한? 방식이 좋은 걸까 싶기도 하고. 처음부터 문제에 유연하게 접근해야 하나 등등의 생각도 들고. 많은 생각이 든다.
일단 이 문제를 통해 배운점은,
그리디 문제의 기준을 세울 때 여러 관점에서 보도록 하자는 것.
일단 조원이 많아질수록 그 조에서 드는 반티값이 많아지니까 나는 단순히 몇 명씩 모아나가야 하는지에 포커스를 맞췄지만, 기존에 이미 한 조를 형성하고 있다고 하고 어느 놈들을 기준으로 분할할지를 고르는 식으로 포커스를 맞췄다면 이 문제를 내 힘으로 풀었을 수 있었을 거다.여러 관점에서 볼 수 있도록 힘을 길러보자.
#9. 코드
import sys
N, K = map(int, sys.stdin.readline().split())
babies = list(map(int, sys.stdin.readline().split()))
diff = []
for i in range(N - 1):
diff.append(babies[i + 1] - babies[i])
diff.sort()
print(sum(diff[:N - K]))
(x1, y1)과 (x2, y2)로 주어지는 두 좌표에 대해 x1 <= x2, y1 <= y2가 성립하며 표는 최대 1024 * 1024사이즈이고 최대 100,000번의 합을 구해야 한다.
무식하게 즉 브루트한 방법으로 푼다면 M번의 트라이에 대해 그 때마다 반복문을 돌며 처리할 수 있다. 그러나 이 방법으로 한다면 최악의 경우 100,000 * 1024 * 1024번의 연산을 해야 하며, 주어진 시간인 1초 내에 통과할 수 없을 것이다.
매번 새로 합을 구하는 것이 아니라 이전에 구한 값을 재활용하는 DP를 통해 문제에 접근해야 한다는 생각이 들었다. 그러나 K번째 트라이에 대한 답을 구할 때 이전 트라이에서 구한 답을 이용해 구할 수 있을지는..
그러다가 풀이방법이 떠올랐다. 누적합을 이용하는 것이다. sum[r][c]가 (0, 0)에서 (r, c)까지의 영역의 합을 의미한다고 하고 (0, 0)부터 (N, N)까지의 모든 sum값을 구해뒀다고 하자. 그렇다면 이를 활용해 임의의 두 좌표 (x1, y1)부터 (x2, y2)의 영역의 합을 sum값을 이리저리 활용해 구할 수 있다! 이 sum값을 구할 때 내가 생각한 방법은
sum[r][c] = sum[r - 1][c] + r번째 행에서 1번 ~ c번값까지의 누적합 이었지만, 다른 사람들의 풀이를 보니
