문제 링크 www.acmicpc.net/problem/2342 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net 풀이 지시 사항의 인덱스, 왼발의 위치, 오른발의 위치를 가지고 dp를 돌려줍시다. 각각 왼발을 옮겼을 때, 오른발을 옮겼을 때로 전개하며, 현재 위치와 다음 위치의 차이에 따른 값만 바꿔주며 정답에 더해주면 됩니다. 정답 코드 #include #define INF 0x3f3f3f3f using namespace std; int d[111'111][5][5]; int..
문제 링크 www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이 www.acmicpc.net 풀이 1) $i$번 학생 바로 앞에 서야하는 다른 학생이 있으면 $i$번 학생의 indegree를 증가시켜줍니다. 2) 순서가 확정된 학생들 외에는 자유롭게 세워도 되므로, indegree가 0인 모든 정점을 큐에 넣습니다. 3) 위상 정렬을 돌립니다. 정답 코드 #include using namespace std; using vi = vector; using vvi ..
문제 링크 www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 풀이 생각 없이 풀 수 있는 백트래킹 문제입니다. 각 행, 열, 3*3 그룹마다 체크 배열을 만들어 두고 1~9까지의 수가 들어 있는지 비트 마스킹으로 확인합니다. 칸 $(i, j)$는 $(i/3)*3 + j/3$ 번째 그룹$(0-based)$에 포함되어있다는 것만 생각해주시면 됩니다. 정답 코드 #include using namespace std; using pii = pair; using v..
문제 링크 www.acmicpc.net/problem/2166 2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 풀이 어떤 삼각형의 세 좌표가 주어졌을 때, 그 삼각형의 넓이는 외적값의 절반입니다. CCW를 구하는데도 외적이 쓰이구요. CCW에 대해선 다음 글을 참고해주세요. CCW로 세 점의 방향성 판별하기 - 데구리 블로그 이걸 확장해서 다각형의 면접을 구할 때도 CCW를 사용할 수 있습니다. 한 점을 기준으로 잡고, 연속한 두 점마다 CCW의 값을 더해준 뒤, 합의 절댓값을 2로 나눠주면 됩니다. 놀랍게도 이 방법은 오목 다각형에도..
문제 링크 www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1≤m≤1,000)이 주어지고, 그 다 www.acmicpc.net 풀이 백준 7453 - 합이 0인 네 정수 문제와 유사합니다. 위 문제에선 $a, b$의 모든조합, $c, d$의 모든 조합을 나눠 생각했고, 이 문제에서는 $a$의 모든 부분 배열의 합, $b$의 모든 부분 배열의 합을 구하여 같은 방식으로 답을 구하면 됩니다. $[T - (a$의 부분 배열$_i$ 의 합)$]$이 $(b$..
문제 링크 www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 풀이 모든 경로를 찾기 위해 dfs를 돌려줍니다. 얼핏 생각하면 복잡도가 터져 나갈 것 같지만 격자 그래프, 작은 범위, 지나간 알파벳은 다시 못 지나간다는 제한 사항 때문에 시간 안에 가능합니다. 저는 알파벳 체킹을 비트 마스크로 했지만 체크 배열을 만들어도 무방합니다. 정답 코드 #include using namespace std; int n, m; string p[22]; int dx[]..
[BOJ] 백준 1799 비숍
문제 링크 www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 풀이 1) 백트래킹을 해야 합니다. 근데 나이브하게 탐색하면 당연히 시간 초과입니다. 2) 우선 어떤 칸의 행, 열로 그 칸이 어떤 대각선에 속해있는지 $O(1)$로 체크할 수 있습니다. 행, 열을 $i, j$라 할 때 오른쪽 위로 가는 대각선을 보면 $(i + j)$값이 같은 칸들이 같은 대각선에 속하고, 오른쪽 아래로 가는 대각선을 보면 $(i - j)$값이 같은 칸들이 같은 대각선에 속합니다. 다만 $(..
문제 링크 www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집 www.acmicpc.net 풀이 1) 문제에서 설명하는 조건은 각 분리된 마을이 최소 스패닝 트리여야 한다는 말입니다. 2) 우선 전체 마을에 대해 최소 스패닝 트리를 만들어주고, 그 트리에서 코스트가 가장 큰 간선을 제거해주면 1)을 만족하며 마을이 두 구역으로 분리됩니다. 정답 코드 #include #define INF 0x3f3f3f3f #define ft first #define s..
문제 링크 www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 풀이 모든 소수는 양수이므로 투 포인터를 적용할 수 있습니다. i, j를 꿈틀꿈틀하게 움직여줍시다. sum + primes[j]가 n 이하이면 sum에 primes[j]를 더해주고 j를 증가, n보다 크면 primes[i]를 빼고 i를 증가시켜줍니다. 정답 코드 #include using namespace std; using ll = long long; using vi = vector; using vb = vector; vi primes; int n; void init() { vb isPrime(4'444'444, tr..