BOJ 문제풀이 (W21)

원래 AC를 받은 문제만 쓰려고 했는데, 그냥 일지처럼 쭉 적어 기록이라도 남겨야겠다는 생각이 들어 앞으로는 못푼 문제도 쓰려고 합니다.

 

18248 제야의 종

가까운 사람일수록 더 많은 종소리를 들을 수 있다는 관찰을 직접 하지는 못했고 도움을 받았습니다.

이후 종소리 들은 횟수가 감소하는 순으로 사람을 정렬시키고 i번째 사람(가까운)은 못 들었는데 i+1번째(먼) 사람이 들은 case가 있으면 false

이렇게 구현하면 해결 할 수 있습니다.

 

7569 토마토

아직 AC받지 못했습니다.

토마토 상자를 입력 받을때 kappa를 줘서 그래프를 쌓고 bfs를 돌려 그래프의 최장 거리를 구해줬는데 틀렸습니다.

 

이미 방문했지만 더 짧은 거리로 갈 수 있다면 이를 que에 넣어줘야 합니다. 이 부분을 추가하고 AC를 받았습니다.

 

16287 parcel

처음에는 two pointer를 이용해 안, 밖을 기준으로 만족하는지 찾아주려 했는데 반례를 받고, 힌트를 얻어 좌우를 나눠 찾는 접근법을 이용해 구현했지만 WA였습니다.

이 문제 역시 디버깅 중 입니다.

 

11277 2 sat-1

변수가 N개뿐이라 $2^N$가지 경우를 설정하고 M개의 절을 확인하는 방식으로 접근 중 입니다.

$O\left ( M2^N \right )$안에 해결 가능해 보입니다.

 

N이 충분히 작아 AC받았습니다.

 

14609 구분구적법

$O\left ( NlogN \right )$ 풀이가 가능해 보입니다.

이분탐색을 돌면서 엡실론값을 전달해주고 받은 엡실론으로 가능한지 N개의 차수를 보면 될 것 같습니다.

 

이분탐색이 생각처럼 돌아가지 않습니다. mid값이 정수만 되네요 디버깅 중 입니다.

 

2461 대표 선수

능력치 순으로 선수들을 정렬하고 투포인터를 이용하여 모든 학급을 커버하는 경우의 max와 min의 값의 차이를 ans에 계속 갱신해주면 됩니다.

이때 전체 학급을 커버하고 있는지 판단을 $O\left ( N \right )$보다 빠르게 해줘야하는데 이는 각 학급의 선수 수를 배열에 저장하고 이 값이 0에서 1로 변할때 cnt++ 1에서 0으로 변할때 cnt--해주면서 카운트해준 값이 n과 같은지 확인해주면 해결 됩니다.

 

 

이번주 내내 추가될 예정입니다