빨간 선과 파란 선
- 제한 시간: 1 초
개의 정점이 있다.
차례마다 다음을 반복해서 개의 정점 사이에 간선을 연결하려고 한다.
- 먼저 2개의 서로 연결되지 않은 정점 와 를 고른다.
- 그 이후, 가 포함된 연결 요소의 모든 정점들 각각에서, 가 포함된 연결 요소의 모든 정점들 각각으로 간선을 추가한다.
-
- 간선의 색은 빨간색 혹은 파란색이다.
번째 차례에 사용할 색깔이 주어질 때, 정점을 골라서 얻을 수 있는 빨간 간선 개수의 최솟값을 구하여라.
입력
- 첫 번째 줄에 정점의 수 이 주어진다.
- 두 번째 줄에 각 차례에 사용할 색깔을 표시하는 개의 수가 공백을 구분으로 주어진다.
-
- 숫자가 이면 빨간 간선을, 이면 파란 간선을 사용한다는 뜻이다.
- 입력되는 모든 수들은 정수이다.
출력
- 문제의 조건을 만족하면서 간선을 연결할 때, 얻을 수 있는 빨간 간선 개수의 최솟값을 출력한다.
입력 예시
5
1 1 0 1
출력 예시
1
- 순서대로 아래와 같이 간선을 연결할 수 있다.
작성코드
n = int(input())
data = list(map(int,input().split()))
Nodes = []
cur = 1
answer = 0
for i in data:
if cur == n:
if i == 1:
Nodes.sort()
Nodes[-2] = Nodes[-1]+Nodes[-2]
Nodes.pop()
else:
Nodes.sort(reverse=True)
answer += Nodes[-1]*Nodes[-2]
Nodes[-2] = Nodes[-1]+Nodes[-2]
Nodes.pop()
continue
if i == 1:
if len(Nodes)==0:
Nodes.append(2)
cur += 2
else:
a = Nodes.index(max(Nodes))
Nodes[a]+=1
cur += 1
else:
if n - cur >= 1:
Nodes.append(2)
answer +=1
cur += 2
else:
a, b = Nodes.index(min(Nodes)), min(Nodes)
answer += Nodes[a]
Nodes[a] += 1
print(answer)
음....... 어렵다.
처음엔 서로소 집합이 생각나긴했는데, 오늘은 조금 NVIDIA로 바빴던날이라;; 제대로 해내지못했다.
내 첼린지는 여기까지인듯 싶다. 아쉽지만.. 좋은 경험이였다 생각한다.
정답코드
C++
#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <algorithm>
using namespace std;
int main() {
int N = 0;
cin >> N;
vector<int> a(N);
for (int i = 0; i < N - 1; i++)
cin >> a[i];
map<vector<int>, int> dp;
dp[vector<int>(N, 1)] = 0;
deque<vector<int>> queue;
queue.emplace_front(N, 1);
while (queue.size()) {
auto v = queue[0];
queue.pop_front();
for (int i = 0; i < v.size(); i++) {
for (int j = i + 1; j < v.size(); j++) {
vector<int> u;
for (int k = 0; k < v.size(); k++) {
if (k == i)
u.push_back(v[i] + v[j]);
else if (k == j)
continue;
else
u.push_back(v[k]);
}
sort(u.begin(), u.end());
if (dp.count(u) == 0) {
queue.push_back(u);
dp[u] = dp[v] + (1 - a[N - v.size()]) * v[i] * v[j];
} else {
dp[u] = min(dp[u], dp[v] + (1 - a[N - v.size()]) * v[i] * v[j]);
}
}
}
}
cout << dp[{N}] << endl;
}
Python
n = int(input())
c = list(map(int,input().split()))
dp = dict()
dp[tuple([1] * n)] = 0
queue = [tuple([1] * n)]
queueIndex = 0
while len(queue) > queueIndex:
v = queue[queueIndex]
queueIndex += 1
for i in range(len(v)):
for j in range(i + 1, len(v)):
u = []
for k in range(len(v)):
if k == j:
u[i] += v[k]
else:
u.append(v[k])
u = tuple(sorted(u))
if u not in dp:
dp[u] = dp[v] + v[i] * v[j] * (1 - c[n - len(v)])
queue.append(u)
else:
dp[u] = min(dp[u], dp[v] + v[i] * v[j] * (1 - c[n - len(v)]))
print(dp[(n,)])
Python
n = int(input())
c = list(map(int,input().split()))
dp = dict()
dp[tuple([1] * n)] = 0
queue = [tuple([1] * n)]
queueIndex = 0
while len(queue) > queueIndex:
v = queue[queueIndex]
queueIndex += 1
for i in range(len(v)):
for j in range(i + 1, len(v)):
u = []
for k in range(len(v)):
if k == j:
u[i] += v[k]
else:
u.append(v[k])
u = tuple(sorted(u))
if u not in dp:
dp[u] = dp[v] + v[i] * v[j] * (1 - c[n - len(v)])
queue.append(u)
else:
dp[u] = min(dp[u], dp[v] + v[i] * v[j] * (1 - c[n - len(v)]))
print(dp[(n,)])
Java
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
int[] a = new int[N - 1];
for (int i = 0; i < N - 1; i++) {
a[i] = scanner.nextInt();
}
Map<List<Integer>, Integer> dp = new HashMap<>();
dp.put(new ArrayList<>(Collections.nCopies(N, 1)), 0);
Deque<List<Integer>> queue = new ArrayDeque<>();
queue.add(new ArrayList<>(Collections.nCopies(N, 1)));
while (!queue.isEmpty()) {
List<Integer> v = queue.pollFirst();
for (int i = 0; i < v.size(); i++) {
for (int j = i + 1; j < v.size(); j++) {
List<Integer> u = new ArrayList<>();
for (int k = 0; k < v.size(); k++) {
if (k == i) {
u.add(v.get(i) + v.get(j));
} else if (k != j) {
u.add(v.get(k));
}
}
Collections.sort(u);
if (!dp.containsKey(u)) {
queue.add(u);
dp.put(u, dp.get(v) + (1 - a[N - v.size()]) * v.get(i) * v.get(j));
} else {
dp.put(u, Math.min(dp.get(u), dp.get(v) + (1 - a[N - v.size()]) * v.get(i) * v.get(j)));
}
}
}
}
System.out.println(dp.get(Collections.singletonList(N)));
}
}
아.. 큐였구나. 흠
'코딩 테스트 > 엘리스 코드 첼린지' 카테고리의 다른 글
[ day 8 ] 강림제 (0) | 2024.07.17 |
---|---|
[ day 7 ] 계기판 조작하기 (1) | 2024.07.16 |
[ day 5 ] 수열 복원 (0) | 2024.07.12 |
[ day 4 ] 트리 위의 게임 (0) | 2024.07.11 |
[ Day 3 ] 문자열 압축 해제 (0) | 2024.07.10 |