specidiee의 티스토리 블로그

[백준] 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광년을 이동한 적이 있어야 하므로..

[백준] 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)에서 ..