신년맞이 boj - day2

신년맞이 작심20일 boj 챌린지

-하루에 정해진 분량만큼 문제 풀이(계획서 참고)

-각 문제별 간단 해결 방법+깃헙 링크 블로그 정리

---

1967 트리의 지름

day1에서 했던 트리의 지름 문제처럼 정점 1에서 가장 멀리 있는 정점을 dfs로 구한뒤, 그 정점에서부터 다시 가장 먼 노드를 찾으면 트리의 지름이 된다

 

github.com/proqk/Algorithm/blob/master/Tree/1967%20%ED%8A%B8%EB%A6%AC%EC%9D%98%20%EC%A7%80%EB%A6%84(2).cpp

 

 

2805 나무 자르기

나무를 세워두고 케이크 자르듯이 칼로 쓰윽 자른다고 생각한다

자른 짜투리의 길이를 전부 더해서 너무 많이 잘랐으면 덜 자르고, 너무 적게 잘랐으면 더 자르는 식으로 조절한다

 

1. 나무를 m만큼 잘라서 나오는 나무의 길이를 더한다

2. 잘린 나무의 합이 필요한 값보다 크면->최대 높이를 갱신한다+높이를 높혀서 덜 자른다

3. 필요한 값보다 작으면 높이를 낮춰서 더 자른다

 

github.com/proqk/Algorithm/blob/master/Bin_search/2805%20%EB%82%98%EB%AC%B4%20%EC%9E%90%EB%A5%B4%EA%B8%B0.cpp

 

 

2512 예산

현재 상한액을 기준으로 예산 합을 구한 뒤에,

예산 합이 전체 예산보다 작으면 상한액을 높게 잡아서 예산을 더 잡는다

예산 합이 예산보다 크면 상한액을 낮게 잡아서 덜 잡는다

 

github.com/proqk/Algorithm/blob/master/Bin_search/2521%20%EC%98%88%EC%82%B0.cpp

 

 

3079 입국 심사

최댓값의 초기값이 문제였는데, int형의 경우 10억을 주면 되지만 long long의 경우 10^18억을 줘야 한다

아니면 약간 주먹구구식으로 10억*10억으로도 되는 것 같다..

 

github.com/proqk/Algorithm/blob/master/Bin_search/3079%20%EC%9E%85%EA%B5%AD%EC%8B%AC%EC%82%AC.cpp

 

 

2613 숫자구슬

이진탐색으로 구슬의 합이 mid랑 비슷하게 구슬을 넣는다

그렇게 만든 그룹과 m을 비교한다. m개의 그룹이 만들어졌을 때만 최종 정답이 된다

m개의 그룹이 만들어지지 않으면 mid를 조정해서 다시 탐색한다

 

github.com/proqk/Algorithm/blob/master/Bin_search/2613%20%EC%88%AB%EC%9E%90%EA%B5%AC%EC%8A%AC.cpp