문제 링크 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[]..
문제 링크 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..