https://www.acmicpc.net/problem/18230
2 × N 크기의 바닥에 2 × 1 크기의 타일 A개와 2 × 2 크기의 타일 B개를 붙이려고 한다. 각 타일들에는 "예쁨"의 정도가 있고, 예쁨이 최대가 되도록 타일링을 하는 문제다.
문제 탐색하기
- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정
ex. 가능한 시간 복잡도, 알고리즘 선택
입출력 제한
- 1 ≤ N, A, B ≤ 2,000
- N ≤ 2 × B + A
- 1 ≤ 예쁨 ≤ 1,000,000
예쁨이 최대가 되도록 하기 위해 입력받은 정수 A개와 B개를 정렬해야 한다. n이 홀수인 경우 A 배열에서 가장 큰 값을 꺼내서 붙여 놓고 시작한다. 이후 A 배열의 큰 값 2개와 B 배열의 큰 값 1개를 비교해 더 큰 것을 붙인다. 타일을 붙이면서 n이나 a, b를 붙인 만큼 줄여야 하고, 붙인 타일을 해당 배열에서 제거해야 한다.
코드 설계하기
위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!
- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지
- N, A, B 입력받기
- 정수 A개와 B개 입력받고 오름차순으로 정렬하기
- N이 홀수면 A 배열에서 맨 뒤에 있는 값을 ans에 더하고 배열에서 제거하기 (n과 a도 1씩 줄이기)
- 반복문 인덱스를 2씩 늘려가면서 반복문 진행
- A 배열 a-1번째와 a-2번째 값을 더한 값과 B 배열 b-1번째 값을 비교해 더 큰 값을 ans에 더하고 배열에서 제거하기
- ans 출력
시도 회차 수정 사항 (Optional)
- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!
pass
정답 코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n,a,b,x,ans;
vector<int> A,B;
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> a >> b;
for (int i=0; i<a; i++) {
cin >> x;
A.push_back(x);
}
for (int i=0; i<b; i++) {
cin >> x;
B.push_back(x);
}
sort(A.begin(),A.end());
sort(B.begin(),B.end());
if (n%2==1) {
ans += A.back();
A.pop_back();
n--;
a--;
}
for (int i=0; i<n; i+=2) {
int ax=0,bx=0;
if (a>=2) {
ax += A[a-1] + A[a-2];
}
if (b>=1) {
bx += B[b-1];
}
if (ax > bx) {
ans += ax;
A.pop_back();
A.pop_back();
a-=2;
}
else {
ans += bx;
B.pop_back();
b-=1;
}
}
cout << ans;
}