hibye1217 hibye1217

난이도: 25 // -705 태그 더보기 Comparison 풀이 1. 사전순으로 더 앞서는 숫자는? 더보기 출력되는 숫자는 \( a \) 또는 \( b \)이기 때문에, 둘 중 사전순으로 더 앞서는 숫자를 출력해야 합니다. 그런데, 사전순으로 더 앞서는 숫자는 그냥 더 작은 숫자죠. 그러므로, \( \min(a, b) \)를 \( \max(a, b) \)회 출력하면 됩니다. 2. 코드 더보기 1 2 3 4 5 void Main(){ int a, b; cin >> a >> b; if (a > b){ swap(a, b); } while (b--){ cout

난이도: 538 태그 더보기 Counting Brute Force 풀이 1. 순서쌍에 대해 생각해보기. 더보기 \( r, g \)가 고정되었다고 해봅시다. 이 때, 가능한 \( b \)의 개수는 얼마나 될까요? \( rR + gG + bB = N \)을 만족시켜야 하는데, \( b \)를 제외하고는 모두 고정된 값이니 가능한 값은 1가지이거나 0가지가 됩니다. 즉, \( r, g \)에 대해서만 브루트포스를 하면서 \( b \)의 가능성 여부를 따지면 되겠죠. 2. \( r, g \)가 고정될 때, 가능한 \( b \)가 존재하는 경우는? 더보기 \( rR + gG + bB = N \)라는 식을 약간 변형해서, \( b \)만 우변에 남겨봅시다. \( b = \frac{N - rR - gG}{B} \) ..

난이도: 11 // -1022 태그 더보기 Arithmetic 풀이 1. 간단한 생각 더보기 간선이 14개밖에 없으니까, 그냥 14개의 pair를 저장하고 풀어도 됩니다. 하지만, 이대로는 재미없으니 뭔가 재밌는 풀이를 들고 와봅시다. 2. 재밌는 생각 더보기 \( x \)와 아래로 연결된 두 수를 잘 보면, 각각 \( 2x \)와 \( 2x+1 \)입니다. \( \left\lfloor \frac{2x}{2} \right\rfloor = \left\lfloor \frac{2x+1}{2} \right\rfloor = x \)이므로, \( a = \left\lfloor \frac{b}{2} \right\rfloor \)인지 판별하는 것만으로도 모든 경우를 다 확인해볼 수 있습니다. 3. 코드 더보기 1234..

난이도: 1777 태그 더보기 Disjoint-Set Union 풀이 1. 1번 쿼리를 생각해보자. 더보기 \( i \)번 상자에 들어있는 공들의 집합을 \( S_{i} \)라고 합시다. 한 쪽 상자의 공을 다른 쪽 상자로 넣는 건, \( S_{X} \)와 \( S_{Y} \)를 합치는 것으로 표현해볼 수 있습니다. 두 집합을 합친다... 뭔가 DSU의 느낌이 나죠? 하지만 DSU에서 상자와 공을 둘 다 들고 있는 건 아무래도 무리가 있어 보입니다. 대신에, 상자를 빼고 공에 대해서만 DSU를 돌려봅시다. 만약 \( X \)번 상자에 있는 공 \( x \)와 \( Y \)번 상자에 있는 공 \( y \)를 알고 있다면, 이를 토대로 \( S_{x} \)와 \( S_{y} \)의 합집합을 구할 수 있겠죠...

난이도: 1119 태그 더보기 Implementation (구현 난이도 조금 있는 편) Coordinate Compression Binary Search 풀이 1. 1차원 버전의 문제를 풀어보자. 더보기 \( 1 \)부터 \( X \)까지의 칸이 있고, 여기에는 \( N \)개의 장애물이 있다고 해봅시다. \( i \)번째 장애물은 \( P_{i} \)에 위치해있으며, 우리가 처리해야 하는 쿼리는 \( dir \) \( x \) \( l \): \( x \)에서 출발해서 \( dir \) 방향으로 \( l \)칸 이동 후 도착하는 위치 출력 입니다. 모든 쿼리에 대해, 이동 결과는 아래 셋 중 하나로 나오게 됩니다. \( l \)칸을 이동하는 동안 장애물을 만나지 않음 장애물을 만나서 도중에 멈춤 마지막..

난이도: 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 ..

난이도: 556 번역 더보기 정점이 \( n \) \( (n \ge 3) \)개인 사이클 그래프가 주어집니다. 사이클 그래프란, 본문의 사진과 같이 \( 1 \)번 정점과 \( 2 \)번 정점이 연결되어있고, \( 2 \)번 정점과 \( 3 \)번 정점이 연결되어있고, ..., \( n-1 \)번 정점과 \( n \)번 정점이 연결되어있고, \( n \)번 정점은 \( 1 \)번 정점과 연결되어있는 그래프를 의미합니다. 당신은 이 그래프에서 일부 정점을 지워서 \( k \)개의 연결 요소만을 남기고 싶어합니다. 정점을 지우게 되면, 그 정점에 연결되어있던 간선들도 같이 지워집니다. 원한다면, 아무 정점도 지우지 않는 것도 가능합니다. 이를 직접 해보기 전에, 정말 \( k \)개의 연결 요소만을 남길 수..

난이도: 8 // -1144 태그 더보기 Arithmetic (사칙연산) Mathematics (수학) 풀이 1. 팔로우할 수 있는 최대 유저 수는? 더보기 \( A \)명이 나를 팔로우하고 있으므로, 문제에서 주어진 식에 따라 \( 2A + 100 \)명을 팔로우할 수 있습니다. 2. 그럼, 몇 명을 더 팔로우할 수 있을까? 더보기 현재 \( B \)명을 팔로우하고 있으므로, 남은 자리는 \( 2A + 100 - B \)명이 되겠네요. 코드 더보기 1 2 3 4 5 void Main(){ int a, b; cin >> a >> b; int x = 2*a+100; cout