221024 문제 풀이 기록

P5 | 1725 - 히스토그램

풀이 시간: 45분

시도 횟수: 10회;

체감 난이도: P5

풀이 쓸 의향: 下

풀이

Monotone Stack으로 stack 관리해주면서 가능한 경우 찾기

여담: 시작점과 끝점인 경우만 세어주고 중간점인 경우를 안 세어놓고 왜 안되는지 오류찾기 하고있었음;; 동일한 문제인 6549번 문제도 겸사겸사 제출함

 

 

 

P3 | 1093 - 스티커 수집

풀이 시간: 1시간 15분

시도 횟수: 10회

체감 난이도: P3

풀이 쓸 의향: 下

풀이

32개의 배열을 16개로 두개씩 나눈 뒤, 2^16가지 각각의 경우에 대해 골랐을 경우의 가격과 가치 값을 저장하자. 왼쪽을 정렬한 뒤 가치는 더 낮은데 가격은 더 높은 경우는 발생하지 않도록 map을 구성한 뒤, 오른쪽 배열에서 이분 탐색을 통해 값 찾아 계산하기

여담: 가지고 있는데 고르지 않았다면 cost를 감소시켜 주는 방식으로 구성했었는데, bit연산을 돌리면서 모든 bit를 순회한 것이 아니라 while (bit>0) 으로 순회하여 가지고 있으나 고르지 않은 경우 몇 가지를 빼놓고 계산하고 있었음.