Day Of Mourning의 기타리스트 강토가 사용하는 기타에서 N개의 줄이 끊어졌다. 따라서 새로운 줄을 사거나 교체해야 한다. 강토는 되도록이면 돈을 적게 쓰려고 한다. 6줄 패키지를 살 수도 있고, 1개 또는 그 이상의 줄을 낱개로 살 수도 있다. 끊어진 기타줄의 개수 N과 기타줄 브랜드 M개가 주어지고, 각각의 브랜드에서 파는 기타줄 6개가 들어있는 패키지의 가격, 낱개로 살 때의 가격이 주어질 때, 적어도 N개를 사기 위해 필요한 돈의 수를 최소로 하는 프로그램을 작성하시오.
[입력] 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주어진다. 가격은 0보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
[출력] 첫째 줄에 기타줄을 적어도 N개 사기 위해 필요한 돈의 최솟값을 출력한다.
✅ 문제 풀이
일단 세트 가격과 낱개 가격의 최소 값을 각각 저장하는 변수를 지정한다.
입력을 받을 때마다 현재의 최소값과 비교하면서, 세트와 낱개의 각각 최소값을 구한다.
기타줄 개수인 N을 6으로 나누었을 때 나머지가 존재하면 그 몫보다 1 큰 만큼을 최소 세트값과 곱한 값, N만큼을 낱개로만 샀을 때의 값, N을 6으로 나누었을 때의 몫 만큼을 최소 세트값과 곱한 값+6으로 나눈 나머지에 최소 낱개값과 곱한 값을 더한, 이 세가지 결과 중 가장 작은 경우가 이 문제의 최종 답이 된다.
✏ 코드 전문
#include<iostream>
#include<algorithm>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N, M;
cin >> N >> M;
int smin = 1000;
int omin = 1000;
for (int i = 0; i < M; i++) {
int s, o;
cin >> s >> o;
smin = min(smin, s);
omin = min(omin, o);
}
int base = smin * (N / 6);
int temp = min((N%6==0) ? base : base + smin, base + (N % 6)*omin);
cout << min(omin * N, temp);
return 0;
}
base의 경우 N이 6의 배수로써 딱 떨어질 수 있고, 나머지가 있을 수 있음.
따라서 세트로만 살 경우에서는, 만약 N이 6배수이면 base 그대로 계산하고, 나머지가 존재한다면 +1하여 계산하도록 하였음.
min함수는 인자를 두개만 받으므로, 세개를 비교하기 위해 두개를 먼저 비교하고 그 결과를 cout으로 바로 나머지 하나와 함께 비교하여 출력하도록 하였음.
서기 2012년! 드디어 2년간 수많은 국민들을 기다리게 한 게임 ACM Craft (Association of Construction Manager Craft)가 발매되었다. 이 게임은 지금까지 나온 게임들과는 다르게 ACM크래프트는 다이나믹한 게임 진행을 위해 건물을 짓는 순서가 정해져 있지 않다. 즉, 첫 번째 게임과 두 번째 게임이 건물을 짓는 순서가 다를 수도 있다. 매 게임시작 시 건물을 짓는 순서가 주어진다. 또한 모든 건물은 각각 건설을 시작하여 완성이 될 때까지 Delay가 존재한다. 위의 예시를 보자. 이번 게임에서는 다음과 같이 건설 순서 규칙이 주어졌다. 1번 건물의 건설이 완료된다면 2번과 3번의 건설을 시작할수 있다. (동시에 진행이 가능하다) 그리고 4번 건물을 짓기 위해서는 2번과 3번 건물이 모두 건설 완료되어야지만 4번건물의 건설을 시작할수 있다. 따라서 4번건물의 건설을 완료하기 위해서는 우선 처음 1번 건물을 건설하는데 10초가 소요된다. 그리고 2번 건물과 3번 건물을 동시에 건설하기 시작하면 2번은 1초뒤에 건설이 완료되지만 아직 3번 건물이 완료되지 않았으므로 4번 건물을 건설할 수 없다. 3번 건물이 완성되고 나면 그때 4번 건물을 지을수 있으므로 4번 건물이 완성되기까지는 총 120초가 소요된다. 프로게이머 최백준은 애인과의 데이트 비용을 마련하기 위해 서강대학교배 ACM크래프트 대회에 참가했다! 최백준은 화려한 컨트롤 실력을 가지고 있기 때문에 모든 경기에서 특정 건물만 짓는다면 무조건 게임에서 이길 수 있다. 그러나 매 게임마다 특정건물을 짓기 위한 순서가 달라지므로 최백준은 좌절하고 있었다. 백준이를 위해 특정건물을 가장 빨리 지을 때까지 걸리는 최소시간을 알아내는 프로그램을 작성해주자.
[입력] 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부터 N번까지 존재한다) 둘째 줄에는 각 건물당 건설에 걸리는 시간 D1, D2, ..., DN이 공백을 사이로 주어진다. 셋째 줄부터 K+2줄까지 건설순서 X Y가 주어진다. (이는 건물 X를 지은 다음에 건물 Y를 짓는 것이 가능하다는 의미이다) 마지막 줄에는 백준이가 승리하기 위해 건설해야 할 건물의 번호 W가 주어진다.
[출력] 건물 W를 건설완료 하는데 드는 최소 시간을 출력한다. 편의상 건물을 짓는 명령을 내리는 데는 시간이 소요되지 않는다고 가정한다. 건설순서는 모든 건물이 건설 가능하도록 주어진다.
문제를 요약하자면..
1번부터 N번까지의 N개의 건물이 있을 때, 주어진 건설 순서 (1 2 = 1->2) 에 따라서 각 건물이 건설될 수 있다.
예를 들어 앞의 그림에 따르면, 2와 3은 1이 건설된 후에야 건설할수 있고, 4는 2와 3이 모두 건설된 후에야 건설할 수 있다.
각 건물을 건설하는데에는 DN의 시간이 소요되고, 입력으로 주어진다.
이때 입력으로 받는 건물 W를 건설하는데 소요되는 최소시간을 구하는 문제이다.
✅ 문제 풀이
W를 건설하기 위해서는 W하위에 연결된 모든 건물이 완료되어야 하기 때문에, W까지 연결되는 여러 경로 중 에서 소요되는 시간이 최대일 때와 같다.
=> 왜 최대이냐?
W가 건설되기 전까지는, W를 건설하기 위해 먼저 건설되어야 하는 건물들 모두가 건설을 마쳐야 W를 건설할 수 있기 때문에, 위의 예시처럼 건물 2가 1초 밖에 걸리지 않다 하더라도, 건물4가 건설되려면 건물3도 건설되어야 하므로, 둘 중 더 소요시간이 긴 건물 3에 의해 100초가 더해져야 한다. 따라서 총 10초(건물1)+100초(건물2,3)+10초(건물4)=120초가 소요된다.
따라서 이 문제는 위상정렬을 이용해서 해결할 수 있다.
다음 사항들을 고려해야 한다.
1. 각 건물(노드)을 건설한 바로 다음에 건설될 수 있는 건물들을 저장해야 한다. => vector<int> node[1005]를 vector 타입의 배열을 만들어서, 각 노드(인덱스=건물번호)에 이전 건물에 대한 정보를 vector로 추가해준다.
2. 각 건물까지 짓는데 걸리는 최소 시간을 저장하는 배열이 있어야 한다.
=> vector<int> sum(1005,0); => 각 노드(인덱스=건물번호)에 저장한다.
3. 각 건물에 대한 깊이를 저장하는 배열이 있어야 한다. => 예시에서 보면 1은 선행 노드가 없으므로 깊이가 0, 2와 3은 선행노드가 1이 있으므로 1, 4는 선행노드가 1, 2-3이 있으므로 2이다.
=> vector<int> degree(1005,0)
이제 코드를 하나씩 만들어가 보자.
테스트 케이스 T를 받아 저장한다.
T번의 테스트 케이스를 진행하도록 for문을 작성하고, for문 안에서 아래 내용들이 동작하도록 구현한다.
건물을 개수를 입력받아 N에 저장한다.
건설 규칙의 개수를 입력받아 K에 저장한다.
다음을 미리 선언해준다. ✔ vector<int> D(1005,0) : 각 건물의 건설시간을 담은 크기가 1005인 벡터 D ✔ vector<int> sum(1005,0) : 각 건물을 완성하기까지 걸리는 시간을 담은 크기가 1005인 벡터 sum ✔ vector<int> node[1005] : 각 건물의 후행 건물을 담은 벡터 타입의 크기가 1005인 배열 node ✔ vector<int> degree(1005,0) : 각 건물(노드)의 깊이를 담은 크기가 1005인 벡터 degree =>값은 모두 0으로 초기화
각 건물의 건설시간을 건물 번호에 맞게 차례로 입력받는다. => 벡터 D의 1번 인덱스부터 1번 건물의 건설 시간을 입력받아 저장한다. => 그리고 sum의 동일한 인덱스에 입력받은 각각의 건설 시간을 저장해준다. sum에는 일단 각 건물에 대한 건설시간이 저장되어 있는 것이다. = 만약 맨 아래 노드라면 해당 건물을 짓는데는 해당 건물의 건설시간만 소요될 것이므로 미리 값을 지정해준다.
K개의 건설 규칙을 입력받자. for문을 연다.
건설 규칙을 입력받기 위해 선행 건물을 저장하는 x와, 후행 건물을 저장하는 y를 선언하고, 입력받아 저장한다.
node[x]에다가 y를 넣어준다. 현재 이 배열은 벡터 타입이므로 push_back하여 y를 저장한다.
그리고 y 이전에 x가 먼저 건설되기 때문에, y는 선행 노드가 있다는 것이므로, degree[y]를 1 늘려줘서 깊이를 1 높인다.
이렇게 K개의 규칙에 대해 다 실행한 후 for문이 끝나면 경로를 하나씩 접근해가며 sum을 갱신할 수 있다.
그 전에 W를 입력받아서 저장해둔다.모든 건물의 sum을 구한 후 그중 sum[W]를 통해 W건물까지 짓는데 걸리는 최소시간을 구할 수 있다. 다음을 진행하여 sum을 설정하자.
queue<int> q를 하나 생성하여 방문할 노드들을 저장하는 용도로 사용하자.
일단 모든 건물(=노드)를 for문을 통해 돌아보면서, 현재 노드의 degree가 0인지 확인한다.
현재 노드의 degree가 0이라면, 선행 노드가 없다는 것이므로, q에 현재 노드를 push한다.
for문을 다 돌면, while문을 통해 q가 빌 때 까지 다음을 수행한다.
q의 맨 앞에 있는 노드를 꺼내 top에 저장한다. 그리고 node[top]에 저장된 모든 후행 노드를 순회하면서 next에 저장한다.
만약 sum[top]+D[next] 가 sum[next]보다 크다면 sum[next]를 전자로 갱신시켜준다. =>이게 바로 같은 레벨에서는 최대로 걸리는 값으로 갱신해야 한다는 의미이다. 같은 레벨에 있는 건물은 다음 건물 짓기 전에 모두 건설완료되어야 하기 때문에 가장 오래 걸리는 건설 시간을 반영한다는 뜻이다.
그리고 degree[next]를 1 줄여서 선행 노드를 이미 방문했음을 표시한다.
그리고 degree[next]가 0이면 이 노드를 시작으로 위 과정을 반복하기 위해 q에 push한다.
그럼 while문을 충족하므로 과정을 반복한다.
맨 마지막 노드에서 degree[next]를 1 줄임으로써 0이 되면서 while문이 종료되고, 각 노드에 대한 최종 sum이 설정되었을 것이다.
그럼 이때 sum[W]를 출력하여 프로그램을 마친다.
☑ 코드 전문
#include<iostream>
#include<string>
#include<vector>
#include<queue>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int T;
cin >> T;
for (int i = 0; i < T; i++) {
int N, K, W, top, next;
vector<int> D(1005, 0);//각 건물의 건설시간
vector<int> node[1005];//노드 별 이어지는 노드
vector<int> degree(1005, 0);//루트로부터 몇번째에 있는지
vector<int> sum(1005, 0);//현재 노드까지의 총 건설 시간
queue<int> q;
cin >> N >> K;
for (int j = 1; j <= N; j++) {
cin >> D[j];
sum[j] = D[j];
}
for (int j = 0; j < K; j++) {
int x, y;
cin >> x >> y;
node[x].push_back(y);
degree[y]++;
}
cin >> W;
for (int j = 1; j <= N; j++) {
if (!degree[j]) {//내 아래로 없으면
q.push(j);//이 노드의 후행 노드들을 살펴보자
}
}
while (!q.empty()) {
top = q.front();
q.pop();
for (int j = 0; j < node[top].size(); j++) {
next = node[top][j];
if (sum[top] + D[next] > sum[next]) sum[next] = sum[top] + D[next];
degree[next]--;
if (!degree[next]) q.push(next);
}
}
cout << sum[W]<<"\n";
}
return 0;
}
옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다. 길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자. S = A[0] × B[0] + ... + A[N-1] × B[N-1] S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다. S의 최솟값을 출력하는 프로그램을 작성하시오.
첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거나 같은 음이 아닌 정수이다.
첫째 줄에 S의 최솟값을 출력한다.
✅ 문제 풀이
크기가 각각 N인 A와 B배열을 입력받은 뒤, B는 그대로 두고, A만 재정렬 하여 A와 B의 원소를 각각 곱해서 최소의 값이 되도록 하는것이다.
여기서 구하고자 하는 것은 그때의 최소값이다.
따라서 A와 B가 어떻게 정렬이 되어 있던 간에, 결국 최소 값을 구하기 위해서는 한쪽은 가장 큰 값, 다른 한쪽은 가장 작은 값을 곱한 것이 최소가 된다.
따라서 A를 오름차순 정렬하고, B를 내림차순 정렬한 후에 각각의 원소끼리 차례로 곱한 값들을 더해주면 최소값이 나오게 된다.
B는 그대로 두되, A를 "재정렬" 하라는 말에 너무 초점을 맞추게 되면, 생각이 많아질 수 있으나, 목적인 최소값을 생각하면 쉽게 해결하는 문제이다.
☑ 코드 전문
#include<iostream>
#include<algorithm>
using namespace std;
bool compare(int a, int b) {
return a > b;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N;
cin >> N;
int *A = new int[N];
int *B = new int[N];
for (int i = 0; i < N; i++) {
cin >> A[i];
}
for (int i = 0; i < N; i++) {
cin >> B[i];
}
sort(A, A + N);//오름차순
sort(B, B + N, compare);//내림차순
int answer = 0;
for (int i = 0; i < N; i++) {
answer += A[i] * B[i];
}
cout << answer;
return 0;
}
1. 선택 절차 : 거스름돈 문제에서 가장 가치가 큰 동전부터 선택 한다. 2. 적절성 검사 : 만약 선택된 동전의 가치가 거스름돈보다 크다면 다음으로 작은 동전을 선택한다. 3. 해답 검사 : 합이 일치하면 거스름돈 문제가 해결된 것이다.
+여기에 부가적인 절차는 주석으로 작성하였다.
#include<iostream>
using namespace std;
int main() {
int N, K;
cin >> N >> K;
int *a = new int[N];
for (int i = 0; i < N; i++) {
cin >> a[i];
}
int cnt = 0; //동전의 개수를 저장할 것이다
for (int i = N - 1; i >= 0; i--) {//문제에서 동전의 가치를 오름차순으로 저장했으므로,뒤에서부터 비교한다
if (a[i] <= K) {//입력받은 가치보다 작은 것중 가장 큰 걸 선택
cnt += (K / a[i]);//큰 가치로 몇번 나누어질 수 있는지를 구하고 더한다
K = K % a[i];//그 나머지를 K로 갱신한다
}
}
cout << cnt;//최종 cnt를 출력한다
}
