개요
SWEA 2115. 벌꿀 채취를 C++로 직접 짰다. 같은 문제를 파이썬으로 정리하고 이론 쪽을 붙인 건 Python - < 6 >에 있다.
문제부터. N×N 격자의 각 칸에 꿀이 든 벌통이 하나씩 있다. 일꾼 두 명을 보내는데, 각 일꾼은 한 행에서 가로로 붙어 있는 M칸을 맡는다. 두 일꾼이 맡은 칸은 겹치면 안 된다. 맡은 M칸을 전부 채취하지는 못하고, 통 용량이 C라 꿀 양의 합이 C 이하가 되도록 골라 담는다. 수익은 채취한 칸의 제곱합이다. 두 일꾼 수익의 합을 최대로 만든다.
정할 게 두 겹이다. 구간 두 개를 어디에 놓을지( 겹치지 않게 ), 그리고 각 구간 안에서 어느 칸을 채취할지( 합이 C 이하가 되게 ).
중간에 진행 방식을 한 번 바꿨다. 그 전까지는 코드를 받아서 읽고 설명을 듣는 쪽이었는데, 어느 순간 이렇게 말했다.
솔직히 니가 준 코드 해석하고 생각만 하는데 더 많은 시간을 보낸 거 같아. cpp로 구현하는 과정도 좀 간략화된 거 같고
그래서 단계별 목표와 기대 출력만 받고 코드는 내가 쓰는 방식으로 바꿨다. 안쪽 결정부터 풀어 올라가는 순서로 넷을 잡았다.
| 단계 | 만드는 것 |
|---|---|
| Step 1 | 입력을 board에 담기 |
| Step 2 |
bestProfit — M칸이 주어졌을 때 최대 수익 |
| Step 3 | 모든 시작 위치의 수익을 미리 계산한 표 |
| Step 4 | 표에서 겹치지 않는 구간 두 개 고르기 |
안쪽 결정인 Step 2부터 올라간다. M칸 하나의 최대 수익이 나와야 구간끼리 비교를 하든 말든 할 테니까.
아래 에러들은 그 뒤로 내가 직접 밟은 것들이다. 그중 하나는 실행하기 전까지 에러가 날 줄도 몰랐다..
Step 1~2 — 입력과 bestProfit
먼저 입력부터.
// N = 벌통 크기, M = 벌통 개수, C = 채취가능 최대 양
int N, M, C;
cin >> N >> M >> C;
vector<vector<int>> board(N, vector<int>(N)); // N x N 격자
for (vector<int>& row : board) // 행을 참조로 받아야 원본에 들어간다
for (int& number : row) cin >> number; // 칸도 참조로 받는다
범위 기반 for를 쓰되 둘 다 참조(&)로 받아야 한다. 값으로 받으면 복사본에 입력이 들어가고 board는 0으로 남는다. C++ - < 1 >에서 정렬 함수에 참조를 안 붙이면 원본이 안 바뀌던 것과 똑같다.
그다음이 bestProfit이다. M칸을 받아서 그 안의 모든 부분집합을 훑고, 합이 C 이하인 것 중 제곱합이 최대인 값을 돌려준다. 바이너리 카운팅으로 짰다.
int bestProfit(vector<int>& cells, int C) // 처음 쓴 시그니처
{
int best = 0;
for (int mask = 0; mask < (1 << cells.size()); ++mask) // M칸의 모든 부분집합
{
int amount = 0, gain = 0; // amount = 꿀 양의 합(C 제한용), gain = 제곱합(수익)
for (int j = 0; j < cells.size(); ++j)
{
if (mask & (1 << j)) // j번 비트가 켜져 있으면 j번 칸을 채취
{
amount += cells[j];
gain += cells[j] * cells[j]; // 누적합이 아니라 이 칸 하나를 제곱한다
}
}
if (amount > C) continue; // 통 용량을 넘으면 이 조합은 버린다
best = max(best, gain);
}
return best;
}
리뷰에서 세 가지가 걸렸다.
-
cells를 non-const 참조로 받았다. 이 함수는 원본을 안 고치는데 시그니처가 그렇게 말하지 않는다 -
int j < cells.size()—size()는 부호 없는 정수라 signed/unsigned 비교 경고가 뜬다 - 제출 전에
freopen을 빼야 한다
amount와 gain을 따로 둔 건 의도한 것이다. 파이썬으로 뼈대를 채울 때 변수 하나에 “합”과 “수익”을 같이 얹었다가 누적합을 제곱하는 버그를 냈었는데, 그걸 겪고 나서 이름을 갈랐다.
그런데 첫 번째 지적이 그냥 스타일 문제가 아니었다.
컴파일 에러 — 실행하기 전엔 에러가 날 줄 몰랐다
bestProfit이 맞게 도는지 보려고 값을 바로 넣어봤다.
cout << bestProfit(vector<int>{6, 5, 5}, 10) << '\n';
빌드가 안 됐다.
error: cannot bind non-const lvalue reference of type 'std::vector<int>&'
to an rvalue of type 'std::vector<int>'
34 | cout << bestProfit(vector<int>{6, 5, 5}, 10) << '\n';
| ~~~~~~~~~~~~~~~~~~~~
note: initializing argument 1 of 'int bestProfit(std::vector<int>&, int)'
7 | int bestProfit (vector<int>& cells, int C)
솔직히 실행하기 전엔 오류가 안 뜰 것 같았다. 값을 넣어서 함수를 부르는 게 전부인데 뭐가 문제냐 싶었다.
원인은 임시 객체였다. vector<int>{6, 5, 5}는 이름이 없고 이 줄이 끝나면 사라지는 값(rvalue)이다. 그런데 vector<int>&는 “이걸 고칠 수도 있다”고 선언한 자리다. 고쳐봐야 곧 사라질 대상이니, C++은 이 조합을 아예 컴파일 단계에서 막는다.
const를 붙이니 됐다.
int bestProfit(const vector<int>& cells, int C)
const 참조는 임시 객체를 받을 수 있고, 받는 동안 그 임시 객체의 수명이 함수 호출이 끝날 때까지 늘어난다. “안 고치겠다”고 약속했으니 사라질 값이어도 안전하다는 논리다.
되짚어보면 파이썬처럼 생각하고 있었다. 파이썬은 모든 인자가 객체 참조로 넘어가고, 리터럴을 넘기든 변수를 넘기든 함수 쪽에서 구분할 수가 없다.
best_profit([6, 5, 5], 10) # 이름이 있든 없든 똑같다
C++에는 그 구분이 있고, 참조의 종류가 그걸 받아낼지를 결정한다.
| 매개변수 | 이름 있는 변수 | 임시 객체 | 복사 |
|---|---|---|---|
vector<int> |
O | O | 한다 |
vector<int>& |
O | X | 안 한다 |
const vector<int>& |
O | O | 안 한다 |
세 번째 줄이 “복사도 안 하고 임시 객체도 받는” 자리다. 앞 편에서 const vector<int>&를 “원본을 안 건드린다고 시그니처로 선언하는 것” 정도로 정리해뒀는데, 여기서 보니 선언만 하는 게 아니라 받을 수 있는 인자의 종류까지 바꾼다.
const를 뒤늦게 붙인 게 스타일 교정인 줄 알았는데, 뒤에서 이게 없으면 코드가 아예 안 돌아갔다!
한 가지 더. VS Code에서 빌드가 깨지면 “빌드가 완료되었지만 오류가 발생했습니다”라는 팝업이 뜨는데, 여기서 디버그를 누르면 이전에 성공했던 exe가 실행된다. 고친 줄 알았던 코드가 아니라 옛날 결과를 보게 되니, 빌드 오류가 뜨면 중단부터 누르는 게 맞다.
Step 3 — 표를 만들다가 범위를 뒤집었다
다음은 전처리다. 시작 위치마다 bestProfit을 미리 계산해 표로 저장해두면, 나중에 두 일꾼을 짝지을 때 계산을 다시 안 해도 된다.
처음 쓴 코드는 이랬다.
map<pair<int, int>, int> profit;
for (int r = 0; r < N - M + 1; ++r) // 행 범위를 N - M + 1로 잡았다
for (int c = 0; c < N; ++c) // 열 범위를 N으로 잡았다
{
pair<int, int> location(r, c); // 시작 좌표를 키로
profit.insert({location, bestProfit(board[r], C)}); // 값은 행 전체를 넘겼다
}
세 군데가 어긋나 있었다.
1. 행과 열의 범위가 뒤바뀌었다. 줄어드는 쪽은 행이 아니라 시작 열이다. 행은 N개 그대로 있고, 한 행 안에서 M칸을 잡을 수 있는 시작 위치가 N − M + 1개다.
2. c를 안 쓰고 있었다. 키에는 (r, c)를 넣어놓고 값은 bestProfit(board[r], C) — 행 전체를 넘겼다. c가 뭐든 같은 값이 나온다.
3. map::insert는 기존 키를 덮어쓰지 않는다. 같은 키가 이미 있으면 조용히 무시하고 넘어간다. 덮어쓰려면 profit[key] = value나 insert_or_assign을 써야 한다. 지금 코드는 키가 안 겹쳐서 드러나지 않았지만, 겹쳤으면 원인 찾느라 꽤 헤맸을 것 같다..
그리고 애초에 map이 필요 없었다. 키가 0부터 연속된 정수 두 개라 2차원 vector면 충분하다. map은 탐색에 O(log n)이 붙고 노드를 따로 잡는다.
이 코드를 그대로 돌리면 어떻게 나올지 예측해봤다. 행은 3개만 나오고, 각 행은 같은 값 네 개가 반복될 것이다. 실제 출력이 이랬다.
85 85 85 85
89 89 89 89
50 50 50 50
예측대로였다. 행 0의 85는 붙어 있지 않은 6과 7을 같이 고른 값이다. 행 전체를 넘겼으니 “가로로 붙은 M칸”이라는 제약이 통째로 빠져 있었다.
나온 값이 틀린 줄도 모를 뻔했다. 85는 그럴듯한 숫자였고, 표 모양도 정상이었다. 행이 3개뿐이라는 게 유일하게 눈에 띄는 단서였다.
구간을 어떻게 넘기나
고친 버전은 이렇다.
// profit[r][c] = r행 c열에서 시작하는 M칸의 최대 수익
vector<vector<int>> profit(N, vector<int>(N - M + 1, 0)); // 행 N개 x 시작 열 (N - M + 1)개
for (int r = 0; r < profit.size(); ++r)
for (int c = 0; c < profit[r].size(); ++c)
profit[r][c] = bestProfit(
vector<int>(board[r].begin() + c, board[r].begin() + c + M), C); // c부터 M칸만 잘라 넘긴다
vector<int>(시작, 끝)은 iterator 두 개로 구간을 잘라 새 벡터를 만드는 생성자다. 파이썬으로 쓰면 이 한 줄이다.
board[r][c:c + M]
둘 다 시작은 포함, 끝은 제외인 반개구간이고, 둘 다 복사본을 만든다.
그런데 이 표현식이 만들어내는 건 이름 없는 임시 객체다. Step 2에서 const를 붙여두지 않았으면 여기서 그대로 막혔다. 그때는 테스트 한 줄 때문에 고친 건 줄 알았는데, 본 코드가 그 형태를 쓰고 있었다.
복사가 아까우면 포인터와 길이로 넘기는 방법이 있다. M이 작아서 이번엔 그냥 뒀다.
Step 4 — 두 일꾼 짝짓기
표가 생기면 남은 건 두 구간을 고르는 일이다. 두 일꾼은 다른 행이거나, 같은 행이면 겹치지 않아야 한다. 두 경우를 따로 계산하고 큰 쪽을 남긴다.
다른 행은 쉽다. 행마다 최댓값을 하나씩 뽑아 정렬하고 큰 것 둘을 더하면 된다. 하나씩만 뽑았으니 둘은 반드시 다른 행이고, 겹칠 수가 없다.
// 행마다 최댓값을 하나씩 모아두고
rowBest.push_back(*max_element(profit[r].begin(), profit[r].end()));
// ... 모든 행을 돈 뒤에
sort(rowBest.begin(), rowBest.end(), greater<int>()); // 내림차순
answer = max(answer, rowBest[0] + rowBest[1]); // 제일 큰 두 개 = 반드시 다른 행
max_element가 iterator를 돌려준다는 게 파이썬의 max(row)와 다르다. 값을 꺼내려면 앞에 *를 붙여야 한다. 최댓값이 몇 번째인지도 같이 필요한 경우가 많으니 이쪽이 기본값인 모양이다.
같은 행은 시작 열 c1, c2가 c1 + M <= c2를 지켜야 한다. 쌍을 전부 보면 행마다 O(N²)인데, c2를 하나 고정해놓고 보면 c1 후보는 0 ~ c2 - M 구간 전체고 그중 최댓값 하나만 있으면 된다.
vector<int> left = profit[r]; // 이 행의 구간별 수익을 복사
for (int c = 1; c < left.size(); ++c)
left[c] = max(left[c - 1], profit[r][c]); // left[c] = 0번부터 c번까지 중 최댓값
for (int c = M; c < left.size(); ++c)
// left[c - M] = c와 겹치지 않는 범위에서 첫 일꾼이 낼 수 있는 최대
answer = max(answer, left[c - M] + profit[r][c]);
left[c]에 0번부터 c번까지 중 가장 좋은 값을 쌓아두면, left[c - M]이 곧 “c와 겹치지 않는 범위에서 첫 번째 일꾼이 낼 수 있는 최대”가 된다. 한 번 훑으면 끝이라 행마다 O(N)이다.
answer = max(answer, ...) 꼴은 bestProfit 안의 best = max(best, gain)과 같은 모양이다. 후보를 하나씩 던지면서 제일 큰 것만 남기는 갱신이다.
최종 코드
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
int bestProfit (const vector<int>& cells, int C)
{
int best = 0;
for (int mask = 0; mask < (1 << cells.size()); ++mask)
{
int amount = 0, gain = 0;
for (int j = 0; j < cells.size(); ++j)
{
if (mask & (1 << j))
{
amount += cells[j];
gain += cells[j] * cells[j];
}
}
if (amount > C) continue;
best = max(best, gain);
}
return best;
}
int main (int argc, char** argv)
{
freopen("sample_input.txt", "r", stdin);
int T;
cin >> T;
for (int test_case = 1; test_case <= T; ++test_case)
{
// N = 벌통 크기, M = 선택 벌통 개수, C = 꿀 채취 최대 양
int N, M, C;
cin >> N >> M >> C;
vector<vector<int>> board(N, vector<int>(N));
for (vector<int>& row : board)
for (int& number : row) cin >> number;
vector<vector<int>> profit(N, vector<int>(N - M + 1, 0));
for (int r = 0;r < profit.size(); ++r)
for (int c = 0;c < profit[r].size(); ++c)
{
pair<int, int> location(r, c); // 시작 좌표 위치
// 시작 좌표에서 시작할 때 최대 이익 저장
profit[r][c] = bestProfit(
vector<int>(board[r].begin() + c, board[r].begin() + c + M), C);
}
int answer = 0;
vector<int> rowBest;
for (int r = 0; r < N; ++r)
{
// 행에서 최댓값 저장
rowBest.push_back(*max_element(profit[r].begin(), profit[r].end()));
// 두 일꾼이 같은 행의 경우 계산
vector<int> left = profit[r];
for (int c = 1; c < left.size(); ++c)
left[c] = max(left[c - 1], profit[r][c]); // 첫번째 작업자의 최대 이득 먼저 계산
for (int c = M; c < left.size(); ++c)
answer = max(answer, left[c - M] + profit[r][c]);
}
sort(rowBest.begin(), rowBest.end(), greater<int>()); // 내림차순 정렬
answer = max(answer, rowBest[0] + rowBest[1]); // 행이 다른 경우 제일 큰 두 수
cout << '#' << test_case << ' ' << answer << '\n';
}
}
샘플 입력 첫 케이스( N = 4, M = 2, C = 13 )를 돌리면 #1 174가 나온다. 중간의 profit 표를 찍어보면 이렇다.
37 82 81
81 89 89
25 41 34
68 40 85
행이 4개, 시작 열이 3개다. 행별 최댓값이 [82, 89, 41, 85]고 상위 두 개가 89( 1행 )와 85( 3행 )니, 서로 다른 행이라 겹칠 일 없이 174가 그대로 답이 된다.
남아 있는 것
-
-Wall -Wextra로 켜면-Wsign-compare경고 5개가 뜬다.int c와size()를 비교하는 줄들이다. 결과에는 영향이 없지만size_t나(int)로 맞춰주는 게 맞다 -
rowBest[1]은 인덱스 검사 없이 읽는다. 이 문제는 N ≥ 3이 보장돼서 안전하지만, 조건이 없으면 그냥 터진다 -
pair<int, int> location(r, c)와#include <map>이 남아 있다.map으로 짰던 첫 버전의 흔적인데, 지금은 아무 데도 안 쓴다 -
freopen은 제출 전에 지워야 한다
다른 언어와 견줘 보면
같은 문제를 두 언어로 짜면서 갈린 지점들이다.
| 개념 | C++ | Python |
|---|---|---|
| 구간 잘라 넘기기 |
vector<int>(it, it + M) 생성자 |
board[r][c:c+M] |
| 임시 객체 전달 | non-const 참조엔 못 넘긴다 | 구분이 없다 |
| 복사 없이 넘기기 | const vector<int>& |
리스트는 기본이 참조 |
| 행 최댓값 |
*max_element(begin, end) ( iterator ) |
max(row) ( 값 ) |
| 내림차순 정렬 | sort(..., greater<int>()) |
sort(reverse=True) |
| 좌표 → 값 표 | 2차원 vector면 충분 |
list 중첩 |
| 제곱 | x * x |
x ** 2 |
pow 대신 x * x를 쓴 건 앞 편 기수 정렬에서 걸렸던 것과 같은 이유다. pow는 double을 다루는 함수라 정수 계산에 쓰면 캐스팅이 붙는다.
그리고 이번 편의 절반은 임시 객체 한 줄에서 나왔다. 파이썬에서 best_profit([6, 5, 5], 10)과 best_profit(cells, 10)은 함수 쪽에서 구분할 방법이 없는데, C++은 그 둘을 다르게 취급하고 매개변수에 const가 있느냐로 받을지 말지가 갈린다. 언어를 옮길 때 진짜 걸리는 건 문법이 아니라 없던 구분이 생기는 것이었다..
소감
문제를 간단한 논리로 풀고(python) 이후에 다시 도메인에 맞춰 C++로 다시 푸니 알고리즘 공부에 도움이 많이 된 하루 였다.