[엘리스][Python] 시즌2. 알고리즘 코드 챌린지 [Day6] - 빨간 선과 파란 선

📚 문제

Day6

 

https://code-challenge.elice.io/courses/282926/lectures/2455429/lecturepages/21567987/list

알고리즘 문제집 | 엘리스 코드 챌린지

---

💡 풀이 과정

• 처음에는 그리디하게 생각했다.
  • 파란색이면 현재에서 가장 많은 선을 그리도록 하고, 빨간색이면 현재에서 가장 적은 선을 그리게 했다.
  • arr 을 [1, 1, ... ] 으로 초기화한다. 이는 모든 노드들이 각각의 그룹이라는 뜻이다.
  • 첫 번째 간선에서는 [1, 1, ... , 2] 로 (n-2) 개의 단일 노드와 2개짜리 그룹 하나가 생성될 것이다.
  • 이후 파란색 간선에서는 최소 간선 수, arr[0] * arr[1] 개를 추가하고 이를 그룹 짓는다.
  • 빨간색 간선에서는 최대 간선 수, arr[-2] * arr[-1] 를 생성한다하고 이를 그룹 짓는다.

n = int(input())
colors = list(map(int, input().split()))

arr = [1 for _ in range(n - 1)]

cnt = 0
for color in colors:
    arr.sort()
    if color == 0:
        cnt += arr[1] * arr[0]
        arr[1] += arr[0]
        arr.pop(0)
    else:
        arr[-2] += arr[-1]
        arr.pop()

print(cnt)

• 대부분의 경우에서는 적용되지만, 반례가 존재한다. 
  • 입력 : 30, 0 0 0 ... 1
  • 출력 : 211
  • 정답 : 210
    • 모든 간선들을 빨간색으로 만들고 마지막 그룹 지을 때 파란색 간선들을 추가하는 경우이다.
    • 이때 [15, 15] 그룹에서 간선을 만드는 것이 파란색 간선을 최대로 만드는 방법이며, 빨간색 간선을 최소로 만드는 방법이다. 
    • 하지만 위와 같이 그리디하게 풀어갈 경우 [14, 16] 그룹만 만들어진다. 
• 그리디가 불가능하고, N <= 30 이기 때문에 bfs 를 진행하기로 했다. 

---

📌 포인트

• str(arr) 으로 visited 체크한다. 
• copy 를 사용해야한다. 사용하지 않으면 stack 에 집어넣은 이후에도 외부에서 변경되면 같이 변경된다.
• 같은 visited 에서도 최소를 체크해서 교체한다. 

---

💻  코드

n = int(input())

arr = [1 for _ in range(n)]
colors = list(map(int, input().split()))

cnt = 0
stack = []
stack.append((arr, 0))
visited = {str(arr): 0}

for color in colors:
    next = []
    while stack:
        ar, c = stack.pop()
        for i in range(len(ar)):
            for j in range(i + 1, len(ar)):
                temp = ar.copy()

                b = temp.pop(j)
                a = temp.pop(i)
                temp.append(a + b)

                temp.sort()
                if color == 0:
                    if str(temp) in visited:
                        if visited[str(temp)] > c + a * b:
                            visited[str(temp)] = c + a * b
                            next.append((temp, c + a * b))
                    else:
                        visited[str(temp)] = c + a * b
                        next.append((temp, c + a * b))
                else:
                    if str(temp) in visited:
                        if visited[str(temp)] > c:
                            visited[str(temp)] = c
                            next.append((temp, c))
                    else:
                        visited[str(temp)] = c
                        next.append((temp, c))
    stack = next
print(min(stack, key=lambda x: x[1])[1])