본문 바로가기

Problem Solving/Baekjoon OJ

(21)
물다이아 희자 적당한? 노력 끝에 Diamond V를 달성했다. 물론 경험치 레이팅 기준이고, AC 레이팅은 아직 2158점으로 Platinum I 수준이다. 난이도 있는 DP와 그리디를 풀었고, 컨벡스 헐을 배워서 기하학 경험치도 올렸다. 아직은 부족하지만 심화 그래프 이론도 조금씩 배우고 있다. 최근엔 위상 정렬을 공부했는데 그래프 치고는 재밌더라. 문자열 관련해서는 손을 놓고 있는데, 사실 심화 알고리즘을 이용해야 하는 문제를 거의 보질 못해서 공부의 필요성을 못 느끼고 있다. AC 레이팅을 올리려면 그래프와 문자열의 공부가 선행되어야 할 것 같다. 개학이 일주일 앞으로 다가왔다. 이젠 정말로 공부를 해야 한다 ㅜ.ㅜ 다른 학생들이 내신 공부를 할 동안 난 알고리즘만 주구장창 했으니 말 다했다. 밀린 숙제들을 조..
(의미 없는) Platinum I 달성 열심히 공부하고 열심히 풀었더니 어느새 플1에 도착했다. 사실 중간에 mobius inversion을 건드리긴 했지만, 최대한 수학 문제를 풀지 않으려고 노력했다. (마지막에는 그냥 수학 밀었다.) 랭작을 의식하지 않다 보니 자연스레 부족한 부분을 채울 수 있었고, 클래스 4도 의도치 않게 획득했다. 하지만 오는 3월부터 티어 시스템이 바뀌게 된다. 들은 바로는 랭킹의 변동을 수월하게 함과 동시에 한 문제가 차지하는 비중을 줄이기 위해서라고 한다. 바뀌게 될 티어를 계산해보니 플3이었고, 클래스 5를 거의 밀었기 때문에 플2까지는 확보할 수 있을 것 같다. 하지만 플2 역시 현재 티어보다는 낮은데, 내가 플레 문제를 많이 풀지 않았기 때문인 것 같다. 물론 티어를 올리는 것이 필수는 아니지만, 변동될 시..
[BOJ 2904] 수학은 너무 쉬워 2904번: 수학은 너무 쉬워 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100) 둘째 줄에는 종이에 적혀있는 수 N개가 주어진다. 수는 모두 1,000,000보다 작거나 같은 양의 정수이다. www.acmicpc.net 예쁘게 구현한 것을 자랑하고 싶어 가져왔다. 관련 테크닉도 자주 쓰이는 듯 하니 기억하자. 더보기 최대공약수를 크게 만들려면 n개의 수에 소인수가 균등하게 분배되어야 하는 것이 자명하다. n개의 수를 모두 곱한 다음 최대한 비슷하게 다시 n개의 수로 쪼갠다고 생각해도 무방하다. 그러나 이동횟수도 구해야 하므로 처음 수는 저장해야 한다. 벡터에 모든 소인수를 저장하고, 맵에 각각의 수의 소인수분해 결과와 합친 결과를 저장한다. 그리고 모든 소인수에 대해 최대공약수와 이동횟수를 갱신해주면 ..
Ruby V 해결 & Platinum II 달성 Platinum III 달성 글을 올린 지 불과 하루 만에, Ruby V 문제를 해결하고 Platinum II를 찍었다. 제비라는 수학 문제였는데, 많게 잡으면 5시간 정도? 걸린 것 같다. 모 채팅방에서 얘기가 나와 도전해봤고, 다행히 헤매지 않고 풀었다. 원래 나는 루비는커녕 다이아도 시도조차 안 하는 겁쟁이었는데, 말도 안 되게 높은 경험치를 보니 눈이 돌아가서 풀게 되었다. 평범한(?) 조합 문제였고, 대충 식을 세워서 식을 예쁘게 정리하니 답을 구할 수 있었다. 식을 정리하는 과정이 너무 지루해 종종 다른 길로 새기도 하였다. 기회가 된다면 다른 분들의 풀이도 들어보고 싶다. (정해를 봤는데 일반항 구하는게 맞더라.) 2021.04.10 수정 : 제비가 모종의 이유로 다이아로 내려갔고, 다시 루..
Platinum III 달성!