백준 문제 풀이 (2.1 ~ 2.8)

시간은 안나지만 최대한 시간을 투자해서 문제를 풀려고 노력하고는 있다....

푼 문제 중에서 플레급 문제만 적어보았다.

 

#9345 - 디지털 비디오 디스크 (DVDs)

재밌는 세그먼트 트리 문제였다.

임의의 칸 두개를 지정하고, 해당 범위의 값을 구한다고 가정해보자.

순서에 상관없이 값만 존재하면 OK이기 때문에, 구간을 대표할 수 있는 값을 찾아야 할 것이다.

간단하게 생각해보면 구간합/최댓값/최솟값이 있을텐데, 곰곰히 생각해보면 최댓값/최솟값 두개만 있으면 해결할 수 있다.

예를 들어, 2~6번째 칸의 최댓값이 6이고, 최솟값이 2라면 그 사이의 값은 반드시 3, 4, 5라는 것이 보장된다.

따라서 최댓값 세그먼트 트리, 최솟값 세그먼트 트리를 각각 만들어서 해결하면 된다.

 

#16975 - 수열과 쿼리 21

구간을 더하고 하나의 값만 가져온다.

대부분 Lazy Propagation을 사용해서 해결하는 것 같은데, 사실 난 아직도 해당 부분을 공부 못 했다...

계~~속 관찰을 해보니 해당 문제는 구간합을 응용하면 해결할 수 있는 문제였다.

구간합 세그먼트 트리를 전부 0으로 초기화 하고, 구간에 더하는 값의 시작 부분과 끝 부분에 해당 수를 더하고 뺀다.

그리고 값 하나를 가져올 때, 1 ~ k번째 합을 가져오면 k번째에 더해진 모든 값을 다 얻어올 수 있다.

 

#8916 - 이진 검색 트리

BST를 시뮬레이팅 한 후, 조합론을 사용하는 문제이다.

K개의 원소가 있고, 1개는 루트, N개는 왼쪽에 있다고 하면, 배치할 수 있는 경우의 수는 (K-1)C(N)임이 보장된다. 이것은 왼쪽/오른쪽의 자식의 수가 0개가 될 때 까지 재귀적으로 곱해지는데, 자식의 수는 처음 BST를 시뮬레이션 하는 과정에서 저장해주면 된다.

 

#9594 - Odd and Even Zeros

굉장히 흥미롭게 풀었더 문제이다.

2 * 5 = 10이 되는데, 어차피 5는 2보다 훨씬 적게 나오므로 2는 신경 쓰지 말고 5가 나오는 횟수만 세면 된다.

자세히 관찰하다보면 신기한 점을 발견할 수 있는데, 5의 제곱수가 나올 때 마다 0의 짝/홀 세는 방법이 뒤집힌다는 점이다.

그래서 5/25/125/625/... 구간에서 0의 수가 짝수인 수의 갯수/0의 수가 홀수인 수의 갯수를 구해주고, 이를 활용해 전체 갯수를 구할 수 있는데, 테이블을 만들고 난 후에 이분탐색을 활용해서 값을 적절하게 더해주면 해결할 수 있다. 

 

#2243 - 사탕 상자

또 세그먼트이다.

1 ~ 1000000이 들어갈 수 있는 구간합 세그먼트 트리를 만들고, 뺄 때만 신경써주면 된다.

뺄 때 현재 적힌 값과 내가 빼려는 값의 대소관계를 비교해서 가지치기를 해주면 쉽게 해결 가능하다.

 

이번주는 하루에 한 문제는 풀 수 있도록 노력해야겠다.