$N$종류의 물약을 모두 구매하려고 하고, 각 물약에는 번호가 매겨져 있습니다. $i$번째 물약의 가격은 동전 $c_i$개이고, 이 물약을 구매하면 $p_i$종류의 다른 물약의 가격이 내려갑니다.
문제에도 나와 있듯이 물약을 구매하는 순서에 따라 전체 물약을 구매하는 비용이 달라질 수도 있습니다. 따라서, 이 문제는 물약을 구매하는 순서를 정하고, 그 다음 물약을 구매하는 비용을 구해야 합니다.
물약의 개수는 $N$개이고, $N$개를 구매하는 순서는 $O(N!)$개가 있습니다. 순서가 결정되면, 이 순서대로 물약을 구매하는 비용을 계산해야 합니다. 각각의 물약을 구매할 때마다, 할인 정보를 이용해서 다른 물약의 비용을 다시 계산해야 합니다. 물약의 할인 정보는 최대 $N-1$개이기 때문에, 물약 하나의 비용을 계산하는데 $O(N)$이 걸립니다. 총 $N$개 물약의 비용을 계산해야 하기 때문에, 전체 물약의 비용을 계산하는데는 $O(N^2)$이 걸립니다. 따라서, 총 $O(N! \times N^2)$이고, $N ≤ 10$이기 때문에 문제의 시간 제한 안에 해결할 수 있습니다.
코딩할 때 물약의 가격이 $0$이하로 내려가지 않는다는 점을 주의해서 구현해야 합니다.
$N$개의 순서를 결정하려면 재귀 호출을 이용하거나, C++의 경우 next_permutation
, Python은 itertools.permutations
을 사용해도 됩니다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<bool> check;
vector<int> order;
vector<int> c;
vector<vector<pair<int,int>>> d;
int go(int index) {
int n = c.size();
if (index == n) {
vector<int> price(c);
int sum = 0;
for (int x : order) {
sum += price[x];
for (auto &p : d[x]) {
int y = p.first;
int z = p.second;
price[y] -= z;
if (price[y] <= 0) price[y] = 1;
}
}
return sum;
}
int ans = -1;
for (int i=0; i<n; i++) {
if (check[i]) continue;
check[i] = true;
order[index] = i;
int cur = go(index+1);
if (ans == -1 || ans > cur) ans = cur;
order[index] = 0;
check[i] = false;
}
return ans;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
check.resize(n);
order.resize(n);
c.resize(n);
for (int i=0; i<n; i++) {
cin >> c[i];
}
d.resize(n);
for (int i=0; i<n; i++) {
int cnt;
cin >> cnt;
for (int j=0; j<cnt; j++) {
pair<int,int> p;
cin >> p.first >> p.second;
p.first -= 1;
d[i].push_back(p);
}
}
int ans = go(0);
cout << ans << endl;
return 0;
}
import java.util.*;
class Pair {
int number;
int price;
Pair(int number, int price) {
this.number = number;
this.price = price;
}
}
public class Main {
static boolean[] check;
static int[] order;
static int[] c;
static Pair[][] d;
static int go(int index) {
int n = c.length;
if (index == n) {
int[] price = c.clone();
int sum = 0;
for (int x : order) {
sum += price[x];
for (Pair p : d[x]) {
int y = p.number;
int z = p.price;
price[y] -= z;
if (price[y] <= 0) price[y] = 1;
}
}
return sum;
}
int ans = -1;
for (int i=0; i<n; i++) {
if (check[i]) continue;
check[i] = true;
order[index] = i;
int cur = go(index+1);
if (ans == -1 || ans > cur) ans = cur;
order[index] = 0;
check[i] = false;
}
return ans;
}
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
check = new boolean[n];
order = new int[n];
c = new int[n];
for (int i=0; i<n; i++) {
c[i] = sc.nextInt();
}
d = new Pair[n][];
for (int i=0; i<n; i++) {
int cnt = sc.nextInt();
d[i] = new Pair[cnt];
for (int j=0; j<cnt; j++) {
int number = sc.nextInt()-1;
int price = sc.nextInt();
d[i][j] = new Pair(number, price);
}
}
int ans = go(0);
System.out.println(ans);
}
}
import sys
input = sys.stdin.readline
n = int(input())
c = list(map(int,input().split()))
d = [[] for _ in range(n)]
for i in range(n):
cnt = int(input())
for _ in range(cnt):
p = list(map(int,input().split()))
p[0] -= 1
d[i].append(p)
check = [False] * n
order = [0] * n
def go(index):
if index == n:
price = c[:]
s = 0
for x in order:
s += price[x]
for p in d[x]:
y, z = p
price[y] -= z
if price[y] <= 0:
price[y] = 1
return s
ans = -1
for i in range(n):
if check[i]:
continue
check[i] = True
order[index] = i
cur = go(index+1)
if ans == -1 or ans > cur:
ans = cur
order[index] = 0;
check[i] = False
return ans
ans = go(0)
print(ans)
먼저, 문제에서는 물약의 번호를 $1$부터 $N$까지로 정의했지만, 소스에서는 $0$부터 $N-1$까지로 바꿔서 문제를 해결했습니다. 따라서, 할인되는 물약 번호를 입력 받을때 $-1$로 번호를 1 빼주었습니다.
소스의 각 변수는 다음을 의미합니다.
n
: 물약의 개수 ($N$)c[i]
: i
번 물약의 가격 ($c_i$)d[i]
: i
번 물약을 구매했을 때, 할인되는 다른 물약의 정보를 담고 있는 배열/리스트d[i][j]
: $(a_j, d_j)$가 저장되어 있음
order[index]
: index
번째로 구매할 물약의 번호
재귀 함수 go(index)
는 index
번째로 구매할 물약의 번호를 정하는 역할을 합니다. 따라서, 모든 물약에 대해서 아직 구매하지 않은 물약을 찾고, 이를 구매했다고 한 다음 index+1
번째 구매할 물약을 찾기 위해 재귀 호출을 수행합니다.
index == n
이면 모든 물약의 구매 순서를 정한 것이기 때문에, 정한 순서대로 물약 구매 비용을 계산해봅니다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> c(n);
for (int i=0; i<n; i++) {
cin >> c[i];
}
vector<vector<pair<int,int>>> d(n);
for (int i=0; i<n; i++) {
int cnt;
cin >> cnt;
for (int j=0; j<cnt; j++) {
pair<int,int> p;
cin >> p.first >> p.second;
p.first -= 1;
d[i].push_back(p);
}
}
int ans = -1;
vector<int> order(n);
for (int i=0; i<n; i++) {
order[i] = i;
}
do {
vector<int> price(c);
int sum = 0;
for (int x : order) {
sum += price[x];
for (auto &p : d[x]) {
int y = p.first;
int z = p.second;
price[y] -= z;
if (price[y] <= 0) price[y] = 1;
}
}
if (ans == -1 || ans > sum) {
ans = sum;
}
} while(next_permutation(order.begin(), order.end()));
cout << ans << endl;
return 0;
}
import sys
import itertools
input = sys.stdin.readline
n = int(input())
c = list(map(int,input().split()))
d = [[] for _ in range(n)]
for i in range(n):
cnt = int(input())
for _ in range(cnt):
p = list(map(int,input().split()))
p[0] -= 1
d[i].append(p)
ans = -1
for order in itertools.permutations(range(n)):
price = c[:]
s = 0
for x in order:
s += price[x]
for p in d[x]:
y, z = p
price[y] -= z
if price[y] <= 0:
price[y] = 1
if ans == -1 or ans > s:
ans = s
print(ans)
소스 2는 소스 1의 재귀 함수를 언어에서 제공하는 함수를 이용한 것입니다. C++은 next_permutation
을 이용했고, Python은 itertools.permutations
를 사용했습니다. Java는 언어에서 제공하는 함수가 없어 구현하지 못했습니다.
같은 집을 두 번 방문하지 않을 경우 그 경로는 유일하다는 조건이 있기 때문에, $x_i$번째 집에서 시작해서 $y_i$번째 집까지 이동하는 경로를 찾는 알고리즘은 DFS 또는 BFS입니다. 그 이유는 DFS와 BFS가 한 정점에서 시작해서 연결된 모든 정점을 방문하는 알고리즘이기 때문입니다.
따라서, $i$ 놀이에서는 $x_i$번째 집을 시작 정점으로 하는 DFS/BFS 알고리즘을 이용해 $y_i$까지 가는 경로를 찾을 수 있습니다. 이제 그 경로 상에 존재하는 모든 집의 대문에 있는 수를 이어 붙여야 합니다.
두 수를 이어 붙이는 방법은 두 가지가 있습니다.
- 두 수를 문자열로 변환한 다음, 이어 붙이고 정수로 변환
- 두 수를 적절한 수식을 통해서 이어 붙임
1번 방법은 소스 3과 같이 구현할 수 있습니다.
int concat(int x, int y) {
string s = to_string(x);
string t = to_string(y);
return stoi(s+t);
}
int concat(int x, int y) {
String s = Integer.toString(x);
String t = Integer.toString(y);
return Integer.parseInt(s+t);
}
def concat(x, y):
s = str(x)
t = str(y)
return int(s+t)
2번 방법을 구현하려면 수가 몇 자리인지 알아야 합니다. 두 정수 $x$와 $y$를 이어 붙일 것이고, $x$의 뒤에 $y$의 자릿수만큼 $0$을 추가한 다음 $y$를 더하면 됩니다. 수 $y$가 $l$자리 수라면 $x$와 $y$를 이어 붙인 수는 $x\times 10^l + y$와 같습니다. 소스 4와 같이 구현할 수 있습니다.
int concat(int x, int y) {
int ans = x;
for (int i=y; i>0; i/=10) {
ans *= 10;
}
ans += y;
return ans;
}
int concat(int x, int y) {
int ans = x;
for (int i=y; i>0; i/=10) {
ans *= 10;
}
ans += y;
return ans;
}
def concat(x, y):
ans = x
i = y
while i > 0:
ans *= 10
i //= 10
ans += y
return ans
두 방법 중 편한 방법을 사용하면 됩니다.
$A_i$는 최대 $10$자리이고, $x_i$번째 집에서 시작해서 $y_i$번째 집까지 이동할 때 이동 경로 상에 있는 집의 최대 개수는 $N$개입니다. $N$은 최대 $1\,000$이니 이어 붙인 수는 최대 $10 \times 1\,000 = 10\,000$ 자리가 됩니다. 이 수는 너무 큰 수이기 때문에, C++, Java에서는 기본 자료형으로 저장할 수 없습니다. Python의 경우에는 저장은 할 수 있지만, 수가 너무 커서 연산이 너무 오래 걸립니다. 이것이 문제에서 $1\,000\,000\,007$로 나눈 나머지를 구하라고 하는 이유입니다.
$(A + B) \text{ mod } C$는 $((A \text{ mod } C) + (B \text{ mod } C)) \text{ mod } C$와 같습니다. 또, $(A \times B) \text{ mod } C$는 $((A \text{ mod } C) \times (B \text{ mod } C)) \text{ mod } C$와 같습니다. 여기서 $\text{mod}$는 나머지 연산입니다.
실제 수가 아닌 나눈 나머지를 구하면 되기 때문에, concat
에서 $1\,000\,000\,007$로 나눈 나머지를 구하게 하면 됩니다. $1\,000\,000\,000$과 $1\,000\,000\,000$를 이어 붙인 수인 $10\,000\,000\,001\,000\,000\,000$이 두 수를 이어 붙였을 때 만들 수 있는 가장 큰 수입니다. 이 값은 C++의 long long
과 Java의 long
범위를 벗어나니 방법 1을 사용하면 올바른 값을 구할 수 없습니다. 따라서, 방법 2를 사용했습니다.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const long long mod = 1'000'000'007;
long long concat(long long x, long long y) {
long long ans = x;
for (long long i=y; i>0; i/=10) {
ans = (ans * 10) % mod;
}
ans += y;
ans %= mod;
return ans;
}
long long bfs(vector<vector<int>> &a, vector<int> &d, int start, int end) {
int n = a.size();
vector<long long> ans(n, -1);
queue<int> q;
q.push(start);
ans[start] = d[start];
while (!q.empty()) {
int x = q.front();
q.pop();
for (int y : a[x]) {
if (ans[y] != -1) continue;
ans[y] = concat(ans[x], d[y]);
q.push(y);
}
}
return ans[end];
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
vector<int> d(n);
for (int i=0; i<n; i++) {
cin >> d[i];
}
vector<vector<int>> a(n);
for (int i=0; i<n-1; i++) {
int u, v;
cin >> u >> v;
u -= 1; v -= 1;
a[u].push_back(v);
a[v].push_back(u);
}
while (q--) {
int u, v;
cin >> u >> v;
cout << bfs(a, d, u-1, v-1) << '\n';
}
}
import java.util.*;
public class Main {
static final long mod = 1_000_000_007;
static long concat(long x, long y) {
long ans = x;
for (long i=y; i>0; i/=10) {
ans = (ans * 10) % mod;
}
ans += y;
ans %= mod;
return ans;
}
static long bfs(ArrayList<Integer>[] a, int[] d, int start, int end) {
int n = a.length;
long[] ans = new long[n];
Arrays.fill(ans, -1);
Queue<Integer> q = new LinkedList<>();
q.add(start);
ans[start] = d[start];
while (!q.isEmpty()) {
int x = q.remove();
for (int y : a[x]) {
if (ans[y] != -1) continue;
ans[y] = concat(ans[x], d[y]);
q.add(y);
}
}
return ans[end];
}
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int q = sc.nextInt();
int[] d = new int[n];
for (int i=0; i<n; i++) {
d[i] = sc.nextInt();
}
ArrayList<Integer>[] a = new ArrayList[n];
for (int i=0; i<n; i++) {
a[i] = new ArrayList<Integer>();
}
for (int i=0; i<n-1; i++) {
int u = sc.nextInt()-1;
int v = sc.nextInt()-1;
a[u].add(v);
a[v].add(u);
}
while (q-- > 0) {
int u = sc.nextInt()-1;
int v = sc.nextInt()-1;
System.out.println(bfs(a, d, u, v));
}
}
}
import sys
from collections import deque
input = sys.stdin.readline
mod = 1_000_000_007
def concat(x, y):
ans = x
i = y
while i > 0:
ans = (ans * 10) % mod
i //= 10
ans += y
ans %= mod
return ans
def bfs(a, d, start, end):
n = len(a)
ans = [-1]*n
q = deque()
q.append(start)
ans[start] = d[start]
while q:
x = q.popleft()
for y in a[x]:
if ans[y] != -1:
continue
ans[y] = concat(ans[x], d[y])
q.append(y)
return ans[end]
n, q = map(int, input().split())
d = list(map(int, input().split()))
a = [[] for _ in range(n)]
for _ in range(n-1):
u, v = map(int, input().split())
u -= 1
v -= 1
a[u].append(v)
a[v].append(u)
for _ in range(q):
u, v = map(int, input().split())
u -= 1
v -= 1
print(bfs(a, d, u, v))
문제에서는 집의 번호를 $1$부터 $N$까지로 정의했지만, 소스 5는 $0$부터 $N-1$까지로 바꿔서 구현했습니다.
소스의 각 변수는 다음을 의미합니다.
n
: 집의 개수 ($N$)q
: 놀이를 한 횟수 ($Q$)d[i]
: i
번 집 대문에 쓰여 있는 수 ($A_i$)a[i]
: i
번 집과 도로 통해 연결된 집의 배열/리스트 (인접 리스트)
각각의 놀이마다 BFS 알고리즘을 수행했습니다.
concat
의 시간 복잡도는 $O($수의 자릿수$)$입니다. BFS는 모든 정점을 한 번씩 방문하는 알고리즘이기 때문에, 시간 복잡도는 $O(N)$입니다. 하지만, 정점을 방문할 때마다 concat
이 한 번씩 호출되어야 합니다. 따라서, bfs
함수의 시간 복잡도는 $O(N \times $수의 최대 자릿수$)$이고, 수의 최대 자릿수는 10이니 $O(10N) = O(N)$으로 나타낼 수 있습니다.
각각의 놀이 결과를 구하기 위해서 bfs
를 한 번 호출합니다. 따라서, 시간 복잡도는 $O(QN)$입니다.