그리디 05 볼링공 고르기

문제를 풀긴 풀었으나 꼼수로 풀었으므로... 해답을 읽고 나서 다시 풀어본다.

(수정 전 코드)

1 2 3 4 5 6 7 8 9 10

import itertools; n, m = map(int, input().split()); balls = list(map(int, input().split())); overlaps = 0; combi = list(itertools.combinations(balls, 2)); balls.sort();   combi = [i for i in combi if i[0] != i[1]];   print(len(combi));

cs

(수정 후 코드)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

balls = [1,3,2,3,2] # [1,5,4,3,2,4,5,2] # list(map(int, input().split())); wgt = 3 #5 #int(input()); wgt_list = [0 for i in range(wgt)]; count = 0;   for ball in balls:   wgt_list[ball - 1] += 1; wgt_list.sort();   while len(wgt_list) > 0:   a = wgt_list.pop();   temp = 0;   for i in wgt_list:     temp += a * i;   count += temp; print(count); Colored by Color Scripter

cs

이 문제에서의 요점은 (가,나)가 뽑은 볼링공의 조합을 구하되, 무게 값이 중복되지 않게 하는 것이다.

문제에서 괜히 볼링공 무게를 언급한게 아니므로 각 무게별로 볼링공이 몇개 인지 기록한다.

그리고 문제에서 조합을 언급 했으므로 (2,3) 과 (3,2)의 결과물은 같은 것으로 취급된다.

(가)가 먼저 뽑은 경우의 수를 기준으로 (나)가 뽑을 것을 상정한 후 경우의 수를 찾는다. 예를 들면 아래와 같다.

---> (가)가 볼링공 3키로를 뽑았으면, (나)는 볼링공 3키로를 뽑지 못한다.

---> (가)가 볼링공 3키로들 중 골라서 하나를 뽑는 경우 * (나)가 나머지 무게의 볼링공들 중 하나를 뽑는 경우.

볼링공에 대한 자료를 아래 두 조건 때문에 무게별로 몇개인지 정리해야 한다.

1. 같은 무게를 (가)와 (나)가 뽑을 수 없다. (3,3) 중복은 안된다.

2. 동일한 무게더라도 볼링공의 index가 다르면 가능하다. 즉 (1,3) 의 중복은 가능하다.

(가)가 볼링공을 먼저 뽑고, (나)가 볼링공을 뽑았을 때의 경우의 수를 순차적으로 더한다.

이 때, 조합이기 때문에 중복 허용이 안되므로 이전 단계에서 (가)가 먼저 뽑아놓았던 것을 제거하며 진행한다.

(1,3)을 먼저 했으면..다음에 (3,1)이 탐색이 안되도록..