본문 바로가기

백준

 (223)
백준 13019 - A를 B로 https://www.acmicpc.net/problem/13019 풀이 일단 서로 가지고 있는 문자가 다르면 문제에 제시된 연산으로 같게 만드는 것이 불가능하므로 -1을 출력한다. 위 조건을 통과하면 답의 초기값을 0으로 설정하고 B의 맨 뒤와 A의 맨 뒤에 포인터(index)를 둬서 서로 비교한다. 둘이 같지 않으면 A의 마지막을 맨 앞으로 보내야 하는 것은 자명하므로 앞으로 보냈다 치고 답을 1 증가시킨다. 두 포인터가 같다면 B의 포인터는 더 볼 의미가 없으므로 B의 포인터에 1을 뺀다. A는 뭐가 되었든 1을 빼면서 모든 문자를 순회한다. 이렇게 A를 순회하면서 증가시킨 값들이 최종 답이다. 뭐? 도대체 무슨 소리를 하고 있는 건지 이해하지 못할 수 있다. 예제 케이스 1번을 보자. 위 방법대로..
백준 2873 - 롤러코스터 https://www.acmicpc.net/problem/2873 분석 문제를 잘 이해하면 가능한 한 지날 수 있는 모든 칸을 지나야 하는 문제임을 알 수 있다. 이 문제의 격자를 체스판으로 생각한다. 시작하는 지점을 흰 칸이라고 가정하자. 그러면 각 이동마다 흰 칸 -> 검은 칸 -> 흰 칸 ->... 이 반복되고 이동을 시작하는 시점에는 지금까지 흰 칸을 지나간 횟수 = 1, 지금까지 검은 칸을 지나간 횟수 = 0 상태가 된다. 이를 이해하면 흰 칸을 지나기 위해선 지금까지 흰 칸을 지나간 횟수 = 지금까지 검은 칸을 지나간 횟수를 만족해야 하고 검은 칸을 지나기 위해선 지금까지 흰 칸을 지나간 횟수 + 1 = 검은 칸을 지나간 횟수를 만족해야 함을 알 수 있다. 이를 토대로 문제를 해결하기 위해 두..
백준 1402 - 아무래도이문제는A번난이도인것같다 https://www.acmicpc.net/problem/1402 힌트 더보기 수열의 길이는 무한으로 둔다. 풀이 풀이는 기술하지 않는다. 제출 기록
백준 17408 - 수열과 쿼리 24 https://www.acmicpc.net/problem/17408 값을 바꾸는 것은 극히 기본적인 세그먼트 트리의 연산이지만 구간 내 두 원소의 합 중 최댓값을 가져오는 연산이 쉽지 않을 수 있다. 다시 생각하면 구간 내 두 원소의 합 중 최댓값은 구간 내에서 가장 큰 값 2개를 가지고 있는 것과 동일하며 해당 쿼리는 구간 내에서 가장 큰 2개의 값을 보존하는 문제로 바뀐다. 가장 큰 2개의 값을 보관하기 위해 C++ 기준 pair를 관리하는 세그먼트 트리를 구성하자. 그러면 왼쪽 절반 L에서 가장 큰 두 값을 저장하는 pair와 오른쪽 절반 R에서 가장 큰 두 값을 저장하는 pair를 가지고 다음 그림처럼 구간을 갱신할 수 있다. 위 그림처럼 가장 큰 두 개의 값을 들고 다니면 된다. 아는 사람은 짐..
백준 2022 - 사다리 https://www.acmicpc.net/problem/2022 사전 지식 본인은 이 문제를 삼분 탐색으로 풀었다. 그 외에도 풀이를 이해하기 위해선 중학교 수준의 기하 지식과 비례식에 대한 이해가 필요하다. 풀이 구하려는 밑변의 길이를 $z = a + b$라고 두자. 그리고 x와 y는 다음과 같이 정리가 가능하다. 하지만 z의 길이를 모르는데 a, b를 구할 수 없다. 우리는 z를 구하는 대신 건물 벽에 접촉한 지점의 높이에 해당하는 옆변의 길이 $w_{x}$, $w_{y}$를 구할 것이다. 이렇게 $w_{x}$와 $w_{y}$를 꺼내면 $w_{x}$와 c, 그리고 $w_{y}$와 c는 각각 $a:a+b = c:w_{y} \; (b:a+b = c:w_{x})$의 비례식으로 표현이 가능함을 발견할 수 ..

티스토리툴바