문제 링크 www.acmicpc.net/problem/2698 2698번: 인접한 비트의 개수 첫째 줄에 테스트 케이스의 수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 수 2개가 공백으로 구분되어 이루어져 있다. 첫 번째 수는 n이고, 두 번째 수는 k이다. n과 www.acmicpc.net 풀이 $\text{D}[i][j][\text{cnt}]$: $i$번째 비트가 $j$이고, 그때 남은 인접한 비트의 수가 $cnt$일 때 조건을 만족하는 수열의 개수 $j$는 $0$ 또는 $1$입니다. 다음과 같이 전개될 수 있습니다. $$\text{D}[i][j][\text{cnt}] = \text{D}[i+1][0][\text{cnt}] + \begin{cases}\te..
문제 링크 www.acmicpc.net/problem/2159 2159번: 케익 배달 첫째 줄에 N이 주어지고 둘째 줄에는 선아가 일하는 레스토랑의 위치가, 셋째 줄부터는 N명의 위치가 X와 Y로 주어진다. 두 좌표 사이에는 공백이 하나 이상 있다. (1 ≤ N, X, Y ≤ 100,000) www.acmicpc.net 풀이 각 주문마다 해당되는 칸과 인접한 4칸, 총 5칸을 갈 수 있는 상태로 정의합니다. 주문과 주문 사이 갈 수 있는 5*5가지 경우의 수로 모두 전이해주면 됩니다. 정답 코드 #include #define INF 0x3f3f3f3f3f3f3f3fLL #define ft first #define sd second using namespace std; using ll = long long..
문제 링크 www.acmicpc.net/problem/16287 16287번: Parcel 입력은 표준입력을 사용한다. 입력의 첫 줄에는 무게 w(10 ≤ w ≤ 799,994)와 A의 원소 개수 n(4 ≤ n ≤ 5,000)이 공백으로 분리되어 주어진다. 다음 줄에는 A의 원소인 n개의 정수 ai ∈ A(1 ≤ i ≤ n)가 www.acmicpc.net 풀이 이번 문제는 카테고리를 너무 의식한 나머지 오래 걸렸던 문제입니다. 사실 크게 보면 DP가 맞긴 한데 일반적으로 생각하는 그런 DP는 아녔습니다. 일단 4개를 한 번에 고르는 경우의 수는 너무 많으니 두 개, 두 개씩 골라 합을 비교하는 방식으로 갑시다. $a_i + a_j + a_k + a_l = W$ 위의 식을 $a_i + a_j = W - (..
문제 링크 www.acmicpc.net/problem/1019 1019번: 책 페이지 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다. www.acmicpc.net 풀이 눈물 줄줄 흘리면서 풀었습니다 ㄹㅇ 이거 제 기준으론 골드 아닙니다.. 아마 더 쉬운 방법으로 구현하거나 규칙을 찾을 수 있을듯한데 그거 생각하는 것만 해도 골드는 아닌 것 같습니다. 백준 9527 - 1의 개수 세기 저는 위 문제와 유사한 방법으로 풀었습니다. 차이점은 2진수가 아니라 10진수고, 0의 개수까지 세주어야 해서 사고 회로가 터져나갑니다. 어쨌든 정답을 구하는 근본 논리는 위 문제와 같습니다. 해당 글을 먼저 참고해주세요. 누적합 배열을 정의해봅시..
문제 링크 www.acmicpc.net/problem/2618 2618번: 경찰차 첫째 줄에는 동서방향 도로의 개수를 나타내는 정수 N(5≤N≤1,000)이 주어진다. 둘째 줄에는 처리해야 하는 사건의 개수를 나타내는 정수 W(1≤W≤1,000)가 주어진다. 셋째 줄부터 (W+2)번째 줄까지 www.acmicpc.net 풀이 저는 경로 추적이 생각보다 까다롭게 느껴졌습니다. 1번, 2번 경찰차가 각각 몇번 사건을 해결했는지를 상태로 둡시다. $i$번 사건을 1번, 2번 경찰차가 해결하는 각 경우에 대해, (경찰차의 마지막 위치 ~ $i$번 사건이 일어난 곳의 위치) 사이 거리를 더해주며 최솟값을 갱신하면 됩니다. 경로추적은 의외로 간단합니다. 발생한 사건을 순서대로 보며, $i$번 사건을 1번 경찰차가 ..
문제 링크 www.acmicpc.net/problem/1006 1006번: 습격자 초라기 하나의 특수 소대로 인접한 두 영역을 커버할 수 있는 배치는 (2,10), (9,16), (4,5), (7,8), (13,14) 이다. 그리고 나머지 6개 구역은 각각 하나의 특수 소대로 커버할 수 있다. 그러므로 최소 11개 특수 소 www.acmicpc.net 풀이 눈물겹게 풀었습니다... 😢😢😢 $i$번 칸의 위아래 각각 1) 선택하지 않음(앞에서 오른쪽 칸을 먹은 상태) 2) 한 칸만 선택 3) 오른쪽과 함께 선택 의 3*3가지 상태와 $i$번의 위, 아래칸을 함께 선택하는 상태로 총 10가지 경우가 있습니다. 각 상태에 따라 어떤 상태로 전이할지 정해주고 DP를 돌리면 됩니다. 맵이 원형이므로 첫 칸에서 가..
문제 링크 www.acmicpc.net/problem/5893 5893번: 17배 첫째 줄에 이진수 N이 주어진다. N은 최대 1000자리인 이진수이며, 0이 들어오는 경우는 없다. www.acmicpc.net 풀이 17 = 10001(2) 입니다. 입력받은 이진수를 왼쪽 4칸 쉬프트 해주고, 다시 그 이진수와 더해주면 17을 곱해준 것과 같습니다. 범위가 크니까 큰 수 덧셈을 구현해줍시다. 정답 코드 #include #define all(x) (x).begin(), (x).end() using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); string u, v, ans; cin >> u; v = u; u +..
문제 링크 www.acmicpc.net/problem/1014 1014번: 컨닝 최백준은 서강대학교에서 “컨닝의 기술”이라는 과목을 가르치고 있다. 이 과목은 상당히 까다롭기로 정평이 나있기 때문에, 몇몇 학생들은 시험을 보는 도중에 다른 사람의 답지를 베끼려 한 www.acmicpc.net 풀이 각 줄마다 사람을 앉힐 수 있는 각 조합을 상태로 생각합니다. 맨 앞줄부터 사람을 채워나간다고 합시다. $d[i][s]$: $i$번 줄에 조합 $s$로 사람을 앉힐 때 현재까지 앉을 수 있는 사람의 최댓값. 조합 $s$를 비트마스킹으로 관리할 수 있습니다. 어떤 자리에 사람을 앉히려고 할 때, 그사람의 바로 앞줄 대각선과 바로 옆에만 사람이 없으면 앉을 수 있습니다. 따라서 단순하게 위의 조건을 만족시키는 두 ..
문제 링크 www.acmicpc.net/problem/1256 1256번: 사전 첫째 줄에 N, M, K가 순서대로 주어진다. N과 M은 100보다 작거나 같은 자연수이고, K는 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 처음부터 예시를 들어 시뮬레이션해봅시다. 모든 과정이 자릿수만 다르지 똑같은 원리로 돌아갑니다. $n = 3, m = 2, k = 3$인 경우를 예로 들어보겠습니다. 1. 정답 구하기 step 1) 첫자리 알파벳을 우선 $a$로 결정한다고 가정합니다. 이때 가능한 문자열은 파랗게 칠한 6가지 문자열입니다. $aaabb$ $aabab$ $aabba$ $abaab$ $ababa$ $abbaa$ $baaab$ $baaba$ $babaa$ $bbaa..
문제 링크 www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 풀이 기본 논리는 간단합니다. 입력받은 두 문자열을 $u$, $v$라 하고, $i$는 $u$의 인덱스, $j$는 $v$의 인덱스라 합시다. 모든 $i$, $j$ 쌍에 대해 탐색하면서, $u[i]$ == $v[j]$ 인 지점에서 다음 문자부터 시작하는 최대 길이의 공통 부분 문자열의 길이값을 가지고 테이블을 업데이트해줍니다. 따로 정답을 저장하는 변수를 두어 그때그때 갱신하면 쉽게 짤 수 있..