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'개의 코인을 보..

[백준] 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의 홀짝성에 따라 분자/분모의 증가 방향이 달라지므..