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$과 겹치는 부분이 있을 수도 있는데, 그렇다면 앞으로 다시 돌아가..