분류 전체보기
-
[26082] WARBOY문제 풀이/Baekjoon Online Judge 2023. 2. 8. 20:21
난이도: Bronze V 태그 더보기 Arithmetic 풀이 1. 성능을 구하기 위한 길 더보기 WARBOY의 성능은, WARBOY의 가격과 가격 대비 성능을 알면 구할 수 있습니다. WARBOY의 가격 대비 성능은, 지문에서 나온대로 경쟁사 제품의 3배입니다. 경쟁사 제품의 가격 대비 성능은, 경쟁사 제품의 가격과 성능으로 알아낼 수 있습니다. 2. 성능을 구하는 식 더보기 경쟁사 제품의 가격 대비 성능 = \( \frac{B}{A} \) WARBOY의 가격 대비 성능 = \( 3 \times \frac{B}{A} \) WARBOY의 성능 = 가격 대비 성능 × 가격 = \( 3 \times \frac{B}{A} \times C \) = \( \frac{3BC}{A} \) 3. 코드 더보기 1 2 3..
-
[25439] 죄수들의 도전문제 풀이/Baekjoon Online Judge 2023. 2. 8. 16:20
난이도: Diamond III 태그 더보기 Ad-Hoc Constructive Divide and Conquer Dynamic Programming 풀이 1. 서브태스크 1만 해보자. (\( N \le 500, m \le 500 \)) 더보기 간단합니다. 1번 죄수는 \( 0 \)을 보고, A를 본 뒤, A에 있는 수를 그대로 적으면 됩니다. 2번 죄수는 \( A \)를 읽고, B를 본 뒤, B에 있는 수와 칠판에 적힌 수 (A)를 비교해서 답을 출력하면 됩니다. 2. 좀 더 효율적으로 비교할 수 없을까? (\( m = 32 \)) 더보기 한 번에 수 전체를 비교하는 대신, 앞에서부터 한 자리씩 비교해나가는 방식을 생각해볼 수 있습니다. 예로, 2169와 2187을 비교한다 해봅시다. 그럼, 처음으로 오..
-
[ABC273 D] LRUD Instructions문제 풀이/AtCoder 2023. 2. 7. 17:31
난이도: 1119 태그 더보기 Implementation (구현 난이도 조금 있는 편) Coordinate Compression Binary Search 풀이 1. 1차원 버전의 문제를 풀어보자. 더보기 \( 1 \)부터 \( X \)까지의 칸이 있고, 여기에는 \( N \)개의 장애물이 있다고 해봅시다. \( i \)번째 장애물은 \( P_{i} \)에 위치해있으며, 우리가 처리해야 하는 쿼리는 \( dir \) \( x \) \( l \): \( x \)에서 출발해서 \( dir \) 방향으로 \( l \)칸 이동 후 도착하는 위치 출력 입니다. 모든 쿼리에 대해, 이동 결과는 아래 셋 중 하나로 나오게 됩니다. \( l \)칸을 이동하는 동안 장애물을 만나지 않음 장애물을 만나서 도중에 멈춤 마지막..
-
[18770] 불안정한 물질문제 풀이/Baekjoon Online Judge 2023. 2. 7. 13:48
난이도: Platinum II 태그 더보기 Functional Graph Dynamic Programming on Tree (트리 DP) on Cycle (원형 DP) // 이거 정식 명칭이 뭐지 Cycle Detection → Tortoise and Hare Depth-First Search 풀이 1. 문제 상황을 요약해보자. 더보기 Functional Graph가 주어질 때, 정점들을 적절히 선택해서 점수 (선택한 정점들에 적힌 수의 합)를 최대화해야 하는 문제입니다. 이 때, 인접한 두 정점을 동시에 선택할 수는 없습니다. 2. Functional Graph가 아니라 Tree였다면? 더보기 잘 알려진 Tree DP 문제가 됩니다. "/ 사회망 서비스(SNS)" 와 비슷한 문제가 되죠. 풀이를 적자면..
-
[1153D] Serval and Rooted Tree문제 풀이/CodeForces 2023. 2. 5. 19:57
난이도: 1900 태그 더보기 Dynamic Programming → DP on Tree (트리에서의 동적 계획법) Greedy (그리디) Depth-First Search (깊이 우선 탐색) 풀이 1. 특정 정점에 쓰인 값을 맨 위로 올려보자. 더보기 특정 값을 맨 위로 올리는 대신, 특정 "정점"을 맨 위로 올려보자는 생각입니다. 그 정점에 쓰인 값을 \( 0 \)이라고 하면, 다른 정점에는 \( 0 \)보다 큰 값이나 \( 0 \)보다 작은 값이 들어가게 됩니다. 이를 각각 \( + \)와 \( - \)라고 표현해봅시다. 2. [1]을 토대로, 특정 정점을 맨 위로 올릴 때 우리가 해야 하는 걸 보자. 더보기 대강 이렇게 생각해보면, 0이 맨 위로 올라간다는 소리는 이 과정에서 만나는 max와 mi..
-
[ARC148 A] mod M문제 풀이/AtCoder 2023. 2. 5. 17:49
난이도: 656 태그 더보기 Number Theory (정수론) Greatest Common Divisor (최대공약수) 풀이 1. 자명하게 생각해볼 수 있는 답의 최댓값은? 더보기 만약 \( M = 2 \)를 선택했다면, 모든 원소는 \( 0 \) 또는 \( 1 \)이 될 테니, 이 때의 답은 최대 \( 2 \)가 됩니다. 2. 그럼, 답이 \( 1 \)인 경우는? 더보기 연산을 1번만 진행할 수 있으니, 모든 \( A_i \text{ mod } M \)이 동일한 \( M \)을 찾아야 합니다. 이를 찾기 위해, 잠시 간단한 경우 \( N = 2 \)를 생각해봅시다. 두 수 \( a, b \)에 대해, \( a \text{ mod } M \)과 \( b \text{ mod } M \)가 같은 \( M ..
-
[19696] Knapsack문제 풀이/Baekjoon Online Judge 2023. 2. 5. 17:31
난이도: Platinum IV 태그 더보기 Dynamic Programming → Knapsack (냅색 문제) Mathematics (수학) Greedy (그리디) Harmonic Sequence 풀이 1. 한 종류의 물건이 여러 개 있는 냅색은 어떻게 풀까? 더보기 가치가 \( v \)이고 무게가 \( w \)인 물건이 \( k \)개가 있다면, 그냥 \( (v, w) \)를 \( k \)개 만들어두면 됩니다. 하지만 이렇게 하면 물건의 개수가 \( NK \)개가 되니까, 너무 많아집니다. 2. (from [1]) 물건의 개수를 줄일 수 없을까? 더보기 1개씩 놓는 건 아무래도 공간 낭비인 것 같습니다. 대신에, 2의 제곱수를 사용해서 더 편하게 표현해봅시다. 이게 무슨 소리냐고요? 어떤 물건이 \(..
-
[ARC030 1] 閉路グラフ문제 풀이/AtCoder 2023. 2. 4. 17:59
난이도: 556 번역 더보기 정점이 \( n \) \( (n \ge 3) \)개인 사이클 그래프가 주어집니다. 사이클 그래프란, 본문의 사진과 같이 \( 1 \)번 정점과 \( 2 \)번 정점이 연결되어있고, \( 2 \)번 정점과 \( 3 \)번 정점이 연결되어있고, ..., \( n-1 \)번 정점과 \( n \)번 정점이 연결되어있고, \( n \)번 정점은 \( 1 \)번 정점과 연결되어있는 그래프를 의미합니다. 당신은 이 그래프에서 일부 정점을 지워서 \( k \)개의 연결 요소만을 남기고 싶어합니다. 정점을 지우게 되면, 그 정점에 연결되어있던 간선들도 같이 지워집니다. 원한다면, 아무 정점도 지우지 않는 것도 가능합니다. 이를 직접 해보기 전에, 정말 \( k \)개의 연결 요소만을 남길 수..