본문 바로가기

알고리즘/백준 문제 풀이

(338)
[C++] 17597번 Zipline https://www.acmicpc.net/problem/17597 25/01/12  간단한 기하학 문제다. 케이스를 나눠서 접근하면 쉽게 해결할 수 있다. 문제 접근 방식:  먼저 두 기둥을 잇는 케이블의 가장 짧은 길이는 두 기둥의 끝을 서로 이은 선분의 길이라는 사실은 쉽게 확인할 수 있다. 이제 케이블의 길이를 점점 늘린다고 해보자.문제에서 주어지는 그림이 케이블을 점점 늘린 상황이라고 가정해보자. 우리는 이 때의 경우에도 케이블 카가 지면으로부터 $r$만큼 위에 있어야 한다는 사실을 알고 있다. 근데 문제는 최저점을 찍었을 때의 상황이 언제인지를 모른다. 케이블 카가 $x$만큼 오른쪽으로 간 상황이라고 해보자. 그러면 케이블의 길이가 다음과 같다. $$l = \sqrt{(g-r)^2 + x^2}..
[C++] 2143번 두 배열의 합 https://www.acmicpc.net/problem/2143 25/01/11  이전에 북마크에 넣어두었다가 해결했던 문제다. 두 가지 해결 방법으로 해결할 수 있는데, 일단 나는 첫번째 해결 방법으로만 해결했고, 나머지 하나는 아이디어만 생각해두어서 적어보려고 한다. 문제 접근 방식:  부 배열의 합은 그냥 연속된 구간 합이다. 당연히 나이브하게 하면 시간초과가 날게 뻔하므로, 각각의 누적 합 배열을 $AA, BB$라고 하자. 이제 문제는 $T$가 주어질 때 $AA[i] - AA[j] + BB[p] - BB[q] = T$를 만족시키는 $i, j, p, q$를 구하는 경우의 수 문제로 바뀌게 되었다. 인덱스를 총 $4$개 뽑아야 되는데, 당연히 나이브하게 이걸 $4$개 뽑아서 조건을 만족시키는 것을 ..
[C++] 32999번 Ribbon on the Christmas Present https://www.acmicpc.net/problem/32999 25/01/06  간단한 그리디+구현 문제다. 문제 접근 방식:  그니깐, 쉽게 생각하면 덧칠한다고 생각하면 된다. 한 번의 붓질로 같은 밝기를 쭉 칠할 수 있는데, 덧칠하면 덧칠할 수록 더 어두워지는 것이다. 근데, 붓질 횟수가 최소가 되려면, 한 번 쭉 붓질할 때 최대한 많은 칸을 칠하는 것이 이득일 것이다. 예를 들어 $[50, 100, 50, 50, 100, 50]$이라면 맨 처음 $50$칠할 때 처음 칸부터 끝 칸까지 칠하고, 이후 2번째, 5번째 칸에 $50$만큼 더 덧칠하면 3번으로 완성할 수 있다. 이걸 코드로 구현해본다면, 기존 주어진 $A$가 있고, 그 배열의 0에 의해 끊어지지 않은 연속된 구간이 있다면 그 구간의 최..
[C++] 33118번 ICPC Provincial https://www.acmicpc.net/problem/33118 25/01/05  간단한 그리디 문제다. 이전에 해결했던 물정 수열과 비슷한 느낌을 받았다. 문제 접근 방식:  2025.01.04 - [알고리즘/백준 문제 풀이] - [C++] 26648번 물정수열 [C++] 26648번 물정수열https://www.acmicpc.net/problem/26648 25/01/04  그리디적으로 생각하면 해결할 수 있는 문제다. 그리디적으로 접근하기 위한 한 가지 핵심적인 관찰이 필요하다. 문제 접근 방식:  한 가지 핵심적인 관lighter.tistory.com이것도 중앙값에 대한 관찰을 해야하는 문제였다. 핵심 관찰은 중앙값을 조절해야 한다는 점이었다. 여기 문제는 길이 $3N$의 수열이 주어질 때 이..
[C++] 25832번 Making Connections https://www.acmicpc.net/problem/25832 25/01/01  약간의 트릭을 가미한 유니온 파인드 문제다. 이 문제를 참 많이 틀렸었는데... 허무하게 원인을 찾아버려서 글로도 남겨보고, 복습도 해보고자 한다. 문제 접근 방식:  결론적으로 틀린 원인만 말하면 long long이슈다. long long자료형을 써야하는데 int를 써서 값이 이상하게 나왔다. 문제는 두 가지 쿼리를 처리해야한다. 첫번째로 두 노드를 합치는 연산. 두 노드를 합친다면 두 노드는 같은 그룹에 속해있게 된다. 두번째로 그래프의 복잡도를 구하는 연산. 이때 모든 그룹의 크기와 그룹의 개수를 구해야 한다. 유파로 처리해보이는건 당연하고, 두번째를 어떻게 빠르게 처리할 지가 의문일 것이다. 따라서 나는 그룹의 ..
[C++] 10246번 부동산 경매 https://www.acmicpc.net/problem/10246 25/01/05  간단한 수식 정리 문제인데, 나이브하게 돌려서 미리 계산해놓고 푸는 풀이도 꽤 빠른 것 같다. 문제 접근 방식:  각 테스트 케이스 별로 다음을 계산하면 된다. 두 수 사이의 연속 된 수들의 합으로 $N$을 표현할 수 있는 경우의 수. 유의할 점은 테스트 케이스의 개수가 안나와있고, 시간 제한은 10초이며, 실제로도 테스트 케이스의 개수가 매우 많다는 점이다. $N$의 범위가 $1 \ 000 \ 000$까지이기 때문에, 어떤 사람들은 미리 그 크기의 배열을 선언해두어 계산을 다 한 후에 쿼리를 처리하는 방식을 하기도 했다.(이 경우 쿼리 당 소요되는 시복도는 상수다.) 나의 경우는 수식으로 접근하여, 쿼리 당 $\mat..
[C++] 28774번 Шестизначные документы https://www.acmicpc.net/problem/28774 25/01/02  백준 땅따먹기에서 나온 문제 중 하나인데, 내가 풀었을 당시에는 골드 4였으나 골드 4치고는 굉장히 어렵다고 느꼈던 문제였다. 이러한 아이디어를 복습해보고자 글을 적어본다. 문제 접근 방식:  일단 문제가 러시아어로 적혀있기 때문에 번역을 하면 다음과 같다. 회계사 발레리(Valeiry)는 회계 보고서에서 불일치를 해결하고 있습니다.그는 총 $n$개의 문서를 확인해야 하며, $i$번째 문서는 여섯 자리 정수 식별자 $a_i$를 통해 회사 네트워크에서 접근할 수 있습니다.역전(inversion)이란, 두 번호 $i$와 $j$($i 배열 ${a_i}$의 복잡성(complexity)은 여섯 자리 각각에서 발생하는 모든 역전의..
[C++] 26648번 물정수열 https://www.acmicpc.net/problem/26648 25/01/04  그리디적으로 생각하면 해결할 수 있는 문제다. 그리디적으로 접근하기 위한 한 가지 핵심적인 관찰이 필요하다. 문제 접근 방식:  한 가지 핵심적인 관찰을 해야한다. 우리는 결국 중앙값이 항상 증가하도록 세 과목 중 한 과목의 점수를 조작할 수 있다.(혹은 조작해야만 한다.) 기존 세 과목의 점수가 $a, b, c$라고 가정하자. 일반성을 잃지 않고, $a  만약 $a$를 더 작게 조작한다고 해도 기존 중앙값 $b$에는 변함이 없다.만약 $a$를 $b$보다 크거나 같고 $c$보다 작도록 조정한다면, 그 조정한 값이 중앙값이 된다.만약 $a$를 $c$보다 크거나 같도록 조정한다면, $c$가 중앙값이 된다. 만약 $b$를 $..