문제 링크 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..
문제 링크 www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 백준 10844 - 쉬운 계단 수 문제에서 모든 수가 한 번 이상 포함되어야 한다는 조건이 추가되었습니다. 쉬운 계단 수와 전개는 똑같이 하되, 현재까지 나온 수들을 집합으로 관리해줍시다. 수의 길이가 n일 때 0번 ~ 9번까지의 모든 비트가 켜져있어야 합니다. 정답 코드 #include using namespace std; using ll = long long; const ll MOD = 1'000'000'000; ll d[(1
문제 링크 www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 (마지막 수 $\pm$ 1)의 방향으로 전개합니다. 길이가 $n$이 될 때까지 전개 가능하면 1을 리턴합니다. 0으로 시작하는 수는 없다는 것에 주의하세요. 해당 처리를 line 16 ~ 22에서 했습니다. 정답 코드 #include using namespace std; using ll = long long; int n; ll d[111][10]; const int MOD = 1'000'000'000; ll go(int l, int last) { if (last 9) return 0;..
문제 링크 www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 풀이 백준 1005 - ACM Craft랑 같은 문제입니다. (어떤 건물을 지을 수 있는 시간 최솟값 + 그 건물을 짓는데 걸리는 시간)이 다음 건물의 d값보다 크면 업데이트해줍니다. 정답 코드 #include using namespace std; using vi = vector; using vvi = vector; int n, cost[555], indeg[555], d[555]; vvi..
문제 링크 www.acmicpc.net/problem/1509 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net 풀이 입력받은 문자열의 $i$번부터 끝까지 해당되는 부분 문자열을 s라 합시다. $d[i]$: $s$를 팰린드롬 분할했을 때 분할 개수의 최솟값. 각 문자열을 두 구간으로 나눠봅니다. $i$부터 시작하는 문자열 s에서 $u = (i$ ~ $j)$, $v = (j+1$ ~ $)$ 이렇게 두 구간으로 나눴을 때 $u$가 팰린드롬이면 $d..