2023.12.23.

백준 1문제

1. BOJ 30985 직장인 파댕이의 사회생활 - G3

약간의 관찰이 요구되는 다익스트라 문제. 

이 문제의 핵심은 어느 방에서 K층까지 전부 올라가는 것만이 최단경로가  될 수 있음을 관찰하는 것이다.

각 층마다의 구조가 모두 동일하다 보니 이게 먹힌다. (안 그랬으면 그래프를 좀 더 조작해서 풀어야 했을 듯.)

그래서 1번 방과 N번 방을 기준으로 다익 두 번 돌려서 모든 방마다의 1번 방과 N번 방의 최단거리를 확인하고,

각 방 별로 K층까지 올라갔을 때의 최단거리가 어떻게 되는지를 비교하면 되었다.

문제가 재밌었다.

 

백준 대회 [첫 번째 나들이] - 3 문제

2. A. 진주로 가자! (Easy) - B3~2 정도로 추측.

문자열 파싱 + 구현 문제. 어렵지 않았다.

 

3. B. 진주로 가자! (Hard) - B1 정도로 추측.

메모리 제한때문에 손을 덜덜떨면서 풀었던 문제.

그 와중에 진주로 가는 cost 제외하고는 범위가 매우 커진걸 모르고 계속 왜 런타임 에러나는가 싶었다.

근데 그냥 1000 넘는 값들은 항상 진주로 가는 비용보다 더 커서 따로 저장하도록 구현하기만 하면 되어 어렵진 않았음.

A번 +1 정도로 예측함. (많아봐야 +2인데 그 정도까지는 아닐듯.)

 

4. C. 선택의 기로 - S4~3...?

Tree set이나 Priorirty_queue 등으로 풀거나 아니면 sorting 함수를 따로 짜서 푸는 문제.

나는 Tree-set으로 구현했는데 구현량이 생각보단 많고 더러웠다.

 

Atcoder (ABC 334) - 3 문제

처음으로 Atcoder 해보는데 문제 유형도 다르고 그래서 매우 당황스러웠다.

뭔 수식 세워서 그걸 프로그래밍으로 푸는 문제들이 이렇게 많은지 모르겠다.

off-by-one 에러 등으로 고통받다가 그냥 도중에 백준 대회로 넘어가서 그거 풀었다.

 

5. A. Christmas Present

백준 기준으로 B5 문제, 값 둘 중에 누가 큰지 비교하는 문제.

 

6. B. Christmas Trees

백준으로는 브론즈 급 문제일듯?

L과 R 사이에 A+kM으로 표현 가능한 값들이 몇 개나 있는지 세는 문제였는데,

근데 각 값의 범위가 매우 커서 수식 세우고 풀어야 했음.

자잘한 오류들이 엄청났어서 여기서 멘탈 터짐.

 

7. D. Reindeer and Sleigh

정렬 + Prefix sum + 이분탐색 문제. 백준으로 치면 실버정도에 위치해 있을 듯.

제일 필요한 사슴 수가 적은 얘들부터 채우면 되니깐 정렬함.

그걸 구간 합으로 먼저 전처리 하고 쿼리별로 이분탐색을 활용해 O(logN) 만에 결과를 찾을 수 있음.

이건 또 수식가지고 장난치는 문제가 아니라서 재밌었음.

차라리 뒤에서부터 풀어보았다면 좀 덜 멘탈이 흔들렸을 것 같다는 생각이 들었다.

 

오늘 일지는 여기서 끝.

그리고 이걸 보는 사람이 있으면 내일 크리스마스 이브인데, 즐겁게 보내시길 바랍니다 :)