💫 오늘의 목표
1. PS 2문제 이상 풀기
오늘도 기출문제 모음에서 풀어보려고 한다.
단, 전에 못푼 문제까지 풀어보고 추가로 문제를 더 풀 생각임!!
1) 주사위 고르기
문제 분석은 3분만에 끝냈다.
구해야 하는건 A의 승률을 높이기 위해 골라야하는 주사위의 오름차순 배열
A가 n개의 주사위 중 반을 가지면 B는 나머지 반을 가짐
고른 주사위들을 굴린 후 모든 경우의 합(이기는 경우의 수)를 구한 뒤 가장 큰 값을 가지는 경우를 리턴하면 됨.
A, B가 주사위를 나눠가지는 경우의 수 : 10C5
주사위를 굴리는 경우의 수 : 6^(N/2) => 최대 6^5
sol 1) 주사위를 나눠가진 후, A와 B를 같이 굴려서 경우를 합산한다.
10C5 x 6^5 x 6^5 = 252 x 60466176 = 2.52 x 6.0466176 x 10^9 => 불가능
sol 2) 주사위를 나눠가진 후, A와 B를 각각 굴려서 저장한다. 그리고 이를 정렬하여 이분탐색으로 구한다.
10C5 x (6^5 + 6^5) x 2x(5xlog5) x log5 = 
불가능은 모호하지만 불안한 정도
sol 3) A 먼저 주사위를 나눠가지고 굴려서 모든 합을 구한다. 그 뒤 B 주사위를 굴리고 모든 합을 구한다. 이후 이분탐색을 돌린다.
정확히는 아래 로직과 같음
10C5 x 6^(n/2) + 6^(n/2)log(6^(n/2))
10^6이어서 안정적으로 돌릴 수 있다.
이렇게 알 수 없는 ArrayIndexOutOfBoundsException 오류가 발생했는데..
메인로직이 잘못된 것이 아닌 변수를 잘못 넘기고 있었다.
arr을 추가할 때 .clone() 메소드를 사용해야하는데 그대로 넘겨서 의도치 않은 에러가 발생한 것...
이를 수정해주니 맞았음
| 정리 전 코드 | 정리 후 코드 (2시간 경과) |
|---|---|
 |  |
전체 캡처를 하니까 중간에 조금 이상해지긴 했지만
한눈에봐도 메인로직을 미리 함수화 시킨 우측코드가 깔끔하다.
상당히 오랜 시간이 걸렸는데, 다음에 다시 풀 때는 더 빨리 풀 수 있기를!
2) [PCCP 기출문제] 2번 / 석유 시추
간단한 BFS문제이고 시간복잡도를 위해 방문배열을 초기화 하지 않는 것
그게 메인인 문제였고, 이런 류의 문제를 많이 풀어봐서 바로 코드로 손이 갔는데
와... 진짜 나는 코드칠 때 생각을 안하는건가 생각이 제대로 들었다.
로직이 틀릴일이 없는데 자꾸 영역별로 숫자 배치가 안되길래 도저히 모르겠어서 chatGPT에게 코드를 줬는데
보고 어라 그러고보니 poll()해놓고 쓴 기억이 없는데 설마 하며 보았더니 정말 정적변수로 쓰고 있었다...
그 오류 찾는다고 30분을 씀
주석필수 주석필수 메인로직 주석.. 꼭 쓰자
3) BOJ 수열과 쿼리 21
오랜만에 백준을 풀어볼까 싶어서 플레문제 중 랜덤으로 돌려봤다.
그런데 결과적으론 구현보다 스니펫이었던...
세그먼트 트리 대표문제였다.
이게 왜 플레인지 잘 모르겠지만 거의 원형 그대로 구현하면 풀렸던 문제
하지만 오랜만에 접한 알고리즘이라 초반 트리 만들 때 구하는 수식은 직접 손으로 계산해서 구했음
자연스레 바로 끄적였던 부분인데 계산을 거쳐야 그 생각까지 닿을 수 있어서 역시 PS는 꾸준하게 해야하는 부분임을 다시 깨달았다.
오늘의 코드 기록
| 전 | 후 |
|---|---|
 |  |
|
