그리디 문제풀이 - 볼링공 선택하기

🔸 볼링공 고르기

A,B 두 사람이 볼링공을 고를 수 있는 조합의 수를 구하는 문제이다.

1. 볼링공 수는 N으로 최대 1,000
2. 볼링공 무게는 M으로 최대 10
3. 서로 같은 무게의 볼링공은 고를 수 없음
4. 같은 무게의 공이 여러 개 존재할 수 있지만, 다른 공으로 간주

📌 예시

5 3

1 3 2 3 2

→ 8가지

8 5

1 5 4 3 2 4 5 2

→ 25가지

📌 초기 접근 방법

A가 첫 번째 공을 골랐다고 가정한다.

1. 1을 골랐으므로, 나머지 공 중 1이 아닌 것의 개수를 구한다.
2. 그 뒤 3을 골랐을 경우, 나머지 공 중 3이 아닌 것의 개수를 구한다.
3. ...

위의 방식으로 첫 번째 공, 두 번째 공, 세 번째 공을 골랐을 때마다

뒤의 공 중 무게가 다른 공의 개수를 합해가며 최종 답을 구하였다.

📌 교재 접근 방법

교재의 방식은 모든 볼링 공의 개수를 카운트한 뒤 풀이를 시작하였다.

따라서 특정 공을 선택했을 시, 해당 공과 다른 무게의 공 중 선택할 수 있는 경우의 수를 합해나갔다.

📌 소스 코드

# 그리디 심화 문제 풀이: 볼링공 고르기
# 최대값 n = 1000, m = 10

# 문제 풀이
def solution(data):
    length = len(data)
    number = []
    sum = 0

    for i in range(length):
        cnt = 0
        for j in range(i, length):
            if data[i] != data[j]:
                cnt += 1
        number.append(cnt)

    for num in number:
        print(num)
        sum += num

    print(sum)

# 교재 풀이
def answer(data, n,m):
    # 1부터 10까지의 무게를 담을 수 있는 리스트
    array = [0]*11

    for x in data:
        array[x] += 1

    result = 0
    # 1부터 m까지의 각 무게에 대하여 처리
    for i in range(1, m+1):
        # 각 무게에 해당하는 볼링공의 개수 카운트
        n -= array[i] # 무게가 i인 볼링공의 개수(A가 선택할 수 있는 개수) 제외
        result += array[i] * n # B가 선택하는 경우의 수와 곱하기

    print(result)


n, m = map(int, input().split())
data = list(map(int, input().split()))

solution(data)

이것이 코딩테스트다 - 나동빈