specidiee의 티스토리 블로그

[백준] 28217 (두 정삼각형)

문제 요약i번째 줄에 i개의 수(0 또는 1)를 배치한 정삼각형 A, B가 주어집니다. i의 최댓값은 N으로 주어집니다. N은 10 이하입니다.A를 원하는 만큼 회전 및 대칭시킬 수 있을 때, B와 동일한 위치에 있는 수의 값이 다른 위치의 개수의 최솟값을 계산해야 합니다.해설해설에 들어가기 전에 2차원 배열에 대해 명확히 해야 할 것이 있습니다. 이 문제를 포함해 일반적으로 2차원 배열을 입력받을 때 다음과 같이 구현합니다.for (int i = 0; i > A[i][j]; }}그런데 입력은 다음과 같이 들어옵니다.A[0][0]A[1][0] A[1][1]A[2][0] A[2][1] A[2][2]따라서 A[i][j]에서 '아래쪽으로 한 칸' 이동하면 A[i + 1][j]이고, '오른쪽으로 한 칸' ..

[백준] 17374 (비트베리)

문제 요약당신은 4종류의 암호화폐 비트, 베리, 코인, 비트코인을 충분히 많이 가지고 있는 친구에게서 아래 다섯 가지 교환을 원하는 만큼 진행할 수 있습니다.비트 A개 → 코인 B개 획득코인 B개 → 비트 A개 획득베리 C개 → 코인 D개 획득코인 D개 → 베리 C개 획득비트 1개 + 코인 1개 → 비트코인 1개 획득정수 A, B, C, D의 값은 테스트 케이스마다 다르게 주어집니다. 현재 당신이 P개의 비트와 Q개의 베리를 보유하고 있을 때, 당신이 가질 수 있는 비트코인의 최대 개수를 구해야 합니다. (정수 P와 Q의 범위는 1만까지입니다)해설먼저, 비트코인을 만드는 과정에 베리는 관계가 없으므로 모든 베리를 코인으로 바꾸고 시작해도 손해가 없습니다. 베리를 코인으로 다 바꾼 뒤에 Q'개의 코인을 보..

[백준] 1011 (Fly me to the Alpha Centauri)

문제 요약공간이동 장치의 작동 방식은 다음과 같은 규칙을 따릅니다:이전 작동 시기에 k광년을 이동했을 때, 다음 작동 시기에서는 k-1, k, 또는 k+1광년만을 이동할 수 있습니다.처음 작동할 경우에는 1광년만 이동할 수 있습니다.도착 지점에 도달하기 바로 직전의 이동 거리는 반드시 1광년이어야 합니다.x 지점에서 정확히 y 지점으로 최소한의 작동 횟수로 이동하려 할 때, 작동 횟수의 최솟값을 계산해야 합니다. (이때, x는 항상 y보다 작습니다.)해설공간이동 장치의 전체 이동 과정에서, 한 번의 작동에 최대 M광년을 이동했다고 합시다. 그러면 M광년을 이동하기 이전에 1, 2, ..., M-1광년을 이동한 적이 있어야 하며, 이동한 후에도 M-1, M-2, ..., 1광년을 이동한 적이 있어야 하므로..

[백준] 5525 (IOIOI)

문제 요약N+1개의 I와 N개의 O로 이루어져 있으며 I, O가 교대로 나오는 문자열을 $P_N$이라고 합시다.I, O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S 안에 $P_N$이 몇 군데 포함되어 있는지 구해야 합니다.N, M의 범위는 100만까지입니다.해설I, O로만 이루어진 긴 문자열(haystack)에서 특정한 문자열(needle)의 매칭 횟수를 선형 시간에 계산해야 하는 문제입니다. 그러한 문제를 일반적으로 해결하기 위한 여러 알고리즘이 있지만, 그것들을 몰라도 이 문제를 풀 수 있습니다.문자열을 왼쪽부터 순회하면서 첫 번째로 매칭되는 $P_N$을 찾습니다. 그 다음으로 매칭되는 $P_N$에는 첫 번째로 매칭된 $P_N$과 겹치는 부분이 있을 수도 있는데, 그렇다면 앞으로 다시 돌아가..

[백준] 31430 (A+B - 투 스텝)

문제 요약이 문제는 투 스텝 문제로, 한 번 채점할 때 프로그램을 2번 실행하는 형식입니다. 두 번의 실행은 서로 독립적입니다.첫 번째 실행에서는 음 아닌 정수 A, B가 주어지며, 소문자 알파벳으로 구성된 길이가 13인 문자열을 출력해야 합니다.두 번째 실행에서는 첫 번째 실행에서 출력한 문자열만 주어지며, A+B의 값을 출력해야 합니다.해설소문자 알파벳으로 구성된 길이가 13인 문자열만으로 두 정수의 합을 나타내야 하므로, 결국 문자열과 숫자를 서로 변환하는 문제를 풀어야 하는 것과 같습니다.소문자 알파벳은 26가지밖에 없는데, 13개를 쓴다면 $2\times 10^{18}$보다 작거나 같은 음 아닌 정수를 모두 표현할 수 있을까요? 다행히 $26^{13}$은 2,481,152,873,203,736,..

[백준] 1193 (분수찾기)

문제 요약무한히 큰 2차원 배열에 다음과 같이 분수들이 적혀 있습니다.1/11/21/31/41/5...2/12/22/32/43/13/23/34/14/25/1...이와 같이 나열된 분수들을 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같이 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 합시다. 정수 X가 주어졌을 때, X번 분수를 계산해야 합니다.X의 범위는 100만까지입니다.해설X번 분수가 D번째 대각선에 있다고 해 봅시다. 두 가지 관찰을 할 수 있습니다:D번째 대각선에는 D개의 분수가 있습니다. 따라서 D번째 대각선의 마지막 번호는 정확히 $\frac{D(D+1)}{2}$가 됩니다.D의 값을 알고 있다면, D의 홀짝성에 따라 분자/분모의 증가 방향이 달라지므..

[백준] 2869 (달팽이는 올라가고 싶다)

문제 요약낮에 A미터 올라갈 수 있지만, 밤에 B미터 미끄러져 내려가는 달팽이가 있습니다. V미터 높이를 올라가야 하는데 정상에 올라간 후에는 미끄러지지 않는다고 할 때, 정상에 오를 때까지 며칠이 걸리는지 계산해야 합니다.해설달팽이가 d일 만에 정상에 오른다고 해 봅시다. 그러면 d-1번의 밤을 겪었고, 그 동안의 누적된 높이는 $(d-1)(A-B)$가 될 것입니다.마지막 날 낮에는 거기서 A만큼 추가로 올라가며, 정상에 도달해서 미끄러지지 않습니다. 따라서 최종 높이는 $(d-1)(A-B)+A$가 되고, 이것이 V 이상이면 됩니다. 즉, $(d-1)(A-B)+A\ge V$찾아낸 부등식을 d에 대해 풀면:$d(A-B)\ge (V-B)$여기서 d는 자연수이므로 $d=\lceil\frac{V-B}{A-B}..

[백준] 2292 (벌집)

문제 요약육각형으로 이루어진 벌집에서, 중앙의 1번 방부터 시작해 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 매깁니다.방 번호 N이 주어졌을 때, 1번 방에서 N번 방까지 최소 개수의 방을 지나갈 때 몇 개의 방을 지나가는지(시작과 끝을 포함하여)를 계산해야 합니다.정수 N은 10억까지 가능합니다.해설1번 방을 중심으로 하는 '육각형 층'의 개념을 생각해 보면, 1번 방만으로 구성된 층이 1층이라고 했을 때, N번 방이 k층에 속해 있다면 문제의 정답은 k가 됩니다.k층의 가장 큰 방 번호를 계산해 볼 수 있습니다. 1층은 1, 2층은 1 + 6 = 7, 3층은 1 + 6 + 12 = 19. 이렇게 계차수열 형태임을 짐작할 수 있고 실제로 k층에 대해서는:$1+6\times 1+6\times 2+\c..

[백준] 10250 (ACM 호텔)

문제 요약호텔에서 손님이 오는 순서대로 방을 배정하는데, 각 층별로 1호실 앞에 있는 엘리베이터 문으로부터 걷는 거리가 짧은 방을 먼저 배정합니다. 단, 거리가 같은 경우에는 층수가 낮은 방을 먼저 배정합니다. 즉 12층짜리 호텔이라면 101, 201, …, 1201호를 먼저 온 12명에게 다 배정하고 13번째 손님에게 102호를 배정하게 됩니다.호텔의 층수 H, 호수 W가 주어졌을 때 N번째 손님에게 배정되어야 하는 방 번호를 구해야 합니다.해설N번째 손님에게 배정되는 방의 층수와 호수를 독립적으로 계산할 수 있습니다.문제의 조건에 따라 i층 j호실은 (j - 1) * H + i번째 손님에게 배정되고, i는 항상 H보다 작거나 같은 정수이므로, N - 1 = (j - 1) * H + (i - 1)에서 ..

티스토리에는 굉장히 오랜만에 글을 적습니다. 오늘은 BOJ에 수록된 '두 배'와 '수열의 장인'이라는 두 문제를 살펴보며 그리디 알고리즘에 수학을 살짝 얹은 유형을 공략해 보겠습니다.문제: 두 배https://www.acmicpc.net/problem/31963KOI 2024 1차대회 초등부, 중등부 기출문제인 '두 배'는 주어진 수열 A를 오름차순으로 만들기 위해 '특정 원소의 값을 2배로 하는 연산'을 여러 번 적용할 수 있을 때 최소 적용 횟수를 구하는 문제입니다.시뮬레이션이 가능할까?처음에 많이들 해 보는 생각이겠지만, [100, 99, 197, 393, ...]과 같은 수열을 생각해보면 시뮬레이션을 진행했을 때 수가 기하급수적으로 빠르게 커질 수 있음을 파악할 수 있습니다.실제로 위 수열을 2배..