기록(記錄)

본문 바로가기

알고리즘

백준 문제 풀이 [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에 의해 끊어지지 않은 연속된 구간이 있다면 그 구간의 최..

수학

회고록

감상록

티스토리툴바