[BOJ 22348] 헬기 착륙장 (C++)
문제 링크
https://www.acmicpc.net/problem/22348
풀이
1+2+3+….+n = (n+1)n/2 를 이용해 dp 테이블을 만들면 된다. 이 문제에서 최대로 사용할 수 있는 페인트 통은 10만개이므로, 반지름은 대략 sqrt(2*10^6)가 최대이다. 계산해보면 대충 450 정도인 것을 알 수 있으나 나는 500으로 정했다.
여기다 현재 착륙장의 크기와 지금까지 사용된 a 페인트의 양을 알면 지금까지 사용된 b 페인트의 양을 자동으로 알 수 있다. 따라서 2차원 배열로 선언하면 된다.
점화식은 지금까지 사용한 전체 페인트 양이 s_ab, 현재까지 사용한 a페인트의 양이 j, 새로 그릴 동심원의 반지름이 i일 때
if (s_ab - j <= b) { // 남은 b 페인트의 양이 충분할 때
dp[i][j] += dp[i - 1][j];
}
if (j - i >= 0) { // a 페인트를 사용 가능할 때
dp[i][j] += dp[i - 1][j - i];
}
대충 이런 식이다. 그러나 어차피 뒤에서 결과값을 구할 때 b의 범위는 알아서 처리하기 때문에 굳이 1번 조건은 쓰지 않아도 된다.
dp[0][0] = 1 로 초기화하고 500*50001 크기의 배열에서 이 작업을 해주면 전처리는 끝.
이제 dp배열을 이용해 i행별 누적합 배열을 새로 만들어주고, a와 b를 새로 받을 때마다 ~450번 계산해주면 된다.
구간은 사진처럼 잡으면 된다.
while (s_ab <= a + b) {
if (s_ab > b) { // b가 제한에 걸렸을 때
long long upper = matrix[i][a]; // a에서 가능한 모든 값의 합
long long lower = matrix[i][s_ab - b - 1]; // b가 모자란 구간의 합
res = (res + upper - lower + MOD) % MOD;
} else {
res = (res + matrix[i][a]) % MOD;
}
++i;
s_ab += i;
}
코드
#include <iostream>
#include <vector>
using namespace std;
const int SIZE = 500;
const int LENGTH = 50000;
const int MOD = 1e9 + 7;
int dp[SIZE][LENGTH + 1];
int matrix[SIZE][LENGTH + 1];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
for (int i = 0; i < SIZE; ++i) {
for (int j = 0; j <= LENGTH; ++j) {
dp[i][j] = 0;
matrix[i][j] = 0;
}
}
dp[0][0] = 1;
int s_ab = 0;
for (int i = 1; i < SIZE; ++i) { //dp 배열 작성
s_ab += i;
for (int j = 0; j <= LENGTH; ++j) {
dp[i][j] = (dp[i][j] + dp[i - 1][j]) % MOD;
if (j - i >= 0) {
dp[i][j] = (dp[i][j] + dp[i - 1][j - i]) % MOD;
}
}
}
for (int i = 1; i < SIZE; ++i) { // 누적합 배열 작성
long long s = 0;
for (int j = 0; j <= LENGTH; ++j) {
s = (s + dp[i][j]) % MOD;
matrix[i][j] = s;
}
}
while (T--) {
int a, b;
cin >> a >> b;
s_ab = 1; // 현재 페인트 사용량
long long res = 0;
int i = 1;
while (s_ab <= a + b) { // 배열에서 답 구하기
if (s_ab > b) {
long long upper = matrix[i][a];
long long lower = matrix[i][s_ab - b - 1];
res = (res + upper - lower + MOD) % MOD;
} else {
res = (res + matrix[i][a]) % MOD;
}
++i;
s_ab += i;
}
cout << res << "\n";
}
return 0;
}
리뷰
누적합을 이용한 dp 문제다. 개인적으로 점화식을 떠올리기는 어렵지 않았다.
그러나 처음에는 Python으로 제출했는데, 서브태스크 중간에 시간초과가 났고(+언어별 추가시간 없음) 더 시간을 줄일 방법은 없는 것 같아서 gpt에게 부탁해 C++로 바꿔달라고 부탁했다. 그런데도 마지막 서브태스크에서 시간 초과가 나는 것이 아닌가!
그래서 생각해낸 것은, a와 b 범위는 이전 서브태스크에서 최대치까지 통과되는 것을 확인했고, 마지막 서브태스크에서는 테스트 케이스만 여러개 들어오는 것을 이용해 미리 ~50000까지의 dp 누적합 테이블을 만들어놓고 빼서 사용하는 방식을 채택했다.
그런데 이번에는 틀렸습니다가 떠서 터졌다. 여기서 멘탈이 약간 흔들렸는데 결국에는 long long 자료형을 쓰지 않아서 생긴 문제였다.(내가 1시간동안 모듈러로 고민한 건 뭐지)
풀고 나서 보니까 다른 사람들은 dp, 누적합 배열을 전부 ll로 선언하고 있었다. 난 메모리가 걱정돼서 배열 자체는 int로 해놓고 누적합 계산하는 부분만 ll로 바꿨는데, 그냥 처음부터 마음 편하게 다 ll로 할 걸 그랬다.
파이썬만 돌리던 자의 최후… 방학 안에 언어를 C++로 교정하는게 목표였는데 갈 길이 멀어 보인다. C++ 형변환을 다시 공부해야 할 듯… 요새 코포도 죽을 쑤고 있어서 기분이 좋지 않은데, 고수의 길은 멀고도 험하구나…
마침
gpt 번역+약간의 수정이라 코드가 썩 깔끔하진 않으니 참고만 하시길 바라며.. 틀린 내용 지적은 언제나 환영입니다!
Leave a comment