[이코테]11-5.볼링공 고르기 문제풀이

이것이 코딩테스트다 파이썬(나동빈 저)

 

그리디 - 볼링공 고르기

 

그리디 문제를 풀다가 

답안지와 다르게 풀어서, 

혹시 나처럼 다른 답안을 찾는 사람들에게 도움이 될까 해서 올린다.

 

문제

 

A,B 두사람이 볼링을 치고 있고, 서로 다른 무게의 볼링공을 고르려고 한다.

볼링공은 총 N개, 공의 번호는 1번부터 순번이다.

같은 무게의 공이 여러개 있을 수 있는데, 다른 공으로 간주한다.

볼링공의 무게는 1~M까지의 자연수이다.

 

입력이

5 3

1 3 2 3 2

라면,

공의 갯수는 5개, 공은 3kg 까지이다. (kg는 임의로 붙인 단위입니다.)

 

1번 공부터 5번까지 공의 무게가 그 다음 줄에 입력된다.

이때 두사람이 고를 수 있는 공 번호의 조합은

1,2  1,3  1,4  1,5  2,3  2,5  3,4  4,5번으로 총 8 경우이다. (각 단위: 번)

 

조합인데, 무게가 중복되지 않아야 한다.

 

코드

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

sum = 0
for i in range(len(lst) - 1):  # 공이 5개일때, 4번째 공에서 5번공 경우까지 계산하므로 -1 해줌
    print(f'\n{i+1}번공 골랐을 때 경우의 수:', len(lst[i+1:]) - lst[i+1:].count(lst[i]))
    print(f'나머지 공들', lst[i+1:], f'갯수에서 {i+1}번공 무게({lst[i]})와 같은 공 갯수 빼주기({len(lst[i+1:])}-{lst[i+1:].count(lst[i])})')
    
    sum += len(lst[i+1:]) - lst[i+1:].count(lst[i])

print(sum)

https://github.com/catalinakim/algorism/blob/master/itcote/greedy/11-5bowlingBall.py

 

프린터 문을 제외하면 코드는 간단하다.

 

입력

5 3 1 3 2 3 2

A가 1번공을 골랐을 때, B가 고를 수 있는 나머지 공에서

A가 고른 공 무게와 같은 공 갯수는 빼주면 된다.

 

1번공 골랐을때, 4경우

2번공 골랐을때, 그 뒤에 공 중에 같은무게 빼면 2경우

3번공 골랐을때, 그 뒤에 상동: 1경우

4번공 골랐을때, 그 뒤에 상동: 1경우 

해서 총 8 경우이다.

 

출력 결과

1번공 골랐을 때 경우의 수: 4 나머지 공들 [3, 2, 3, 2] 갯수에서 1번공 무게(1)와 같은 공 갯수 빼주기(4-0) 2번공 골랐을 때 경우의 수: 2 나머지 공들 [2, 3, 2] 갯수에서 2번공 무게(3)와 같은 공 갯수 빼주기(3-1) 3번공 골랐을 때 경우의 수: 1 나머지 공들 [3, 2] 갯수에서 3번공 무게(2)와 같은 공 갯수 빼주기(2-1) 4번공 골랐을 때 경우의 수: 1 나머지 공들 [2] 갯수에서 4번공 무게(3)와 같은 공 갯수 빼주기(1-0) 8

 

공이 10kg 까지 밖에 없기 때문에, 

볼링공의 갯수가 많아진다면

책에서의 풀이처럼 무게별로 갯수를 카운팅해놓고 계산하는 것이 더 효율적이다.

 

다음 번엔 그와 같은 방식으로 풀어봐야겠다.