💡 PS
[BOJ] 1114 통나무 자르기
date
Mar 1, 2022
slug
boj-1114
author
status
Public
tags
PS
summary
통나무 자르기에 대한 문제 풀이입니다.
type
Post
thumbnail
category
💡 PS
updatedAt
Aug 3, 2023 09:02 AM
언어
문제
풀이
휴게소 세우기 문제와 상당부분 비슷하다. 차이점이 있다면 통나무를 자를 수 있는 위치가 정해져 있다는 것과 처음 자르는 위치도 같이 출력해야 한다는 것이다.
이분탐색 하는 부분은 동일하다. 가능한 범위중 가장 작은 값인 1을
le, 가장 큰 값인 l을 ri로 설정하였다.mi가 가장 긴 조각의 길이가 될 수 있는지 chk()함수에서 확인한다.11번째줄 :
sm은 현재까지 더해진 통나무의 길이이다. cnt는 통나무를 자른 횟수이다.12~14번째줄 : 가능한 것이 여러개일 경우, 처음 자르는 위치가 최소가 되어야 한다. 따라서 뒤쪽부터 확인하며 길이가
t를 넘지 않는 선에서 최대한 sm에 더해준다. 만약 자를 수 있는 두 지점사이의 거리가 t보다 클 경우 불가능하므로 바로 -1을 리턴해준다.15~18번째줄 :
sm이 t보다 클 경우, 직전에서 통나무를 잘라야 한다. 따라서 sm도 바꿔줘야 한다.19~22번째줄 : 만약
cnt가 문제에서 제한한 c와 같을 경우, 더 이상 자를 수 없다. 하지만 arr[i]가 t보다 클 경우 통나무를 추가로 잘라줘야 하므로 -1을 리턴한다. 그렇지 않을 경우, 처음 자르는 위치인 arr[i]을 리턴한다. (위에서 cnt가 하나 증가해 19번째에서 조건이 걸리는거기 때문.)24번째줄:
cnt가 c보다 작은 경우이므로 추가로 통나무를 자를 수 있는 가장 작은 위치를 리턴한다.코드
#include <cstdio> #include <algorithm> #include <queue> using namespace std; int l, k, c, ans; int arr[10002]; vector<int> v; int chk(int t) { int sm = 0, cnt = 0; for(int i = v.size()-1; i >= 0; i--) { if (v[i] > t) return -1; sm += v[i]; if (sm > t) { cnt++; sm = v[i]; } if (cnt == c) { if (t < arr[i]) return -1; return arr[i]; } } return arr[0]; } void go() { int le = 1, ri = l; while (le < ri) { int mi = (le + ri) / 2; int t = chk(mi); if (t > -1) { ans = t; ri = mi; } else le = mi + 1; } printf("%d %d", ri, ans); } int main() { scanf("%d %d %d", &l, &k, &c); for(int i = 0; i < k; i++) scanf("%d", &arr[i]); arr[k] = l; sort(arr, arr + k+1); v.push_back(arr[0]); for(int i = 1; i < k+1; i++) v.push_back(arr[i] - arr[i-1]); go(); }