[ day 6 ] 파란 선과 빨간 선

빨간 선과 파란 선

• 제한 시간: 1 초

N개의 정점이 있다.
차례마다 다음을 반복해서 N개의 정점 사이에 간선을 연결하려고 한다.

• 먼저 2개의 서로 연결되지 않은 정점 u와 v를 고른다.
• 그 이후, u가 포함된 연결 요소의 모든 정점들 각각에서, v가 포함된 연결 요소의 모든 정점들 각각으로 간선을 추가한다.
• • 간선의 색은 빨간색 혹은 파란색이다.

k번째 차례에 사용할 색깔이 주어질 때, 정점을 골라서 얻을 수 있는 빨간 간선 개수의 최솟값을 구하여라.

 

입력

• 첫 번째 줄에 정점의 수 N이 주어진다.
  
  2≤N≤30
• 두 번째 줄에 각 차례에 사용할 색깔을 표시하는 N−1개의 수가 공백을 구분으로 주어진다.
• • 숫자가 0이면 빨간 간선을, 1이면 파란 간선을 사용한다는 뜻이다.
• 입력되는 모든 수들은 정수이다.

---

출력

• 문제의 조건을 만족하면서 간선을 연결할 때, 얻을 수 있는 빨간 간선 개수의 최솟값을 출력한다.

---

입력 예시

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)));
    }
}

 

아.. 큐였구나. 흠