[리뷰] 그리디 - 볼링공 고르기

github.com/ndb796/python-for-coding-test

ndb796/python-for-coding-test

오랜만에 글을 올립니다.

늘 그렇듯 책을 사서 보시길 바랍니다.

이 문제의 포인트는 1번과 2번을 선택하는 것과 2번과 1번을 선택하는 것은 같다고 봅니다.

조합(combination)을 생각하시면 이해하기 빠르리라 믿습니다.

 

직관적으로 생각하면 특정 숫자를 뽑으면 그것만 제외한 나머지 숫자를 선택하면 됩니다. 

그렇다면 첫번째 for 문은 그냥 단순희 리스트를 순회한다고하면

----->

여기서 중복을 피해야하므로

뽑은 숫자를 비교하는 연산은 for문을 처음부터 비교하는 것이 아니라 뽑은 숫자 뒤의 숫자들을 순회합니다.

아래의 화살표와 같이 

예1)

------>

  ---->

예2)

------->

     -->

 

이런식으로 비교하면 두번째 사람은 첫번쨰 사람이 픽 했었던 공을 선택하지 않기 때문에 중복이 발생하지 않습니다.

 

python

import sys
n, m = map(int,input().split())
arr = list(map(int, sys.stdin.readline().rstrip().split()))
visited = [0  for _ in range(n+1)]

count =0
for i in range(n):
  if visited[i] == 1:
    continue
  else:
    for j in range(i+1,n):
      if arr[i] == arr[j]:
        continue
      else:
        count += 1

    visited[i] = 1

print(count)

c++

#include <bits/stdc++.h>

using namespace std;

int main(){

  int n, m;
  int cnt=0;
  cin>>n>>m;
  vector<int> v;
  int visited[10001]= {0};
  for(int i =0; i < n; i++){
    int tmp;
    cin>>tmp;
    v.push_back(tmp);
  }

  for(int i= 0;i<n;i++){
    if(visited[i] == 1) continue;
    for(int j = i+1; j<n;j++){
      if(v[i] == v[j]){
        continue;
      }
      cnt++;
    }
    visited[i] = 1;
  }
  cout<<cnt<<'\n';
}

여기서 다시 그리디하게 생각을 해봅시다.

전체 선택 가능한 경우의 수는 n입니다.

무게는 최대 m(3으로 가정하자)까지 있을 수 있습니다.

 

무게 1을 선택하면 무게 2이상의 합, 즉 전체 - 무게 1의 수라고 이해할 수 있습니다.

1을 선택하는 경우의 수 가 1, 전체 수가 5이면 그 외의 숫자들의 합은 4

그래서 선택하는 방법의 수는 1 * 4 = 4입니다

 

무게 2를 선택하면 1을 더이상 선택할 이유가 없습니다. 이미 위에서 계산을 했기 때문입니다.

무게 2를 선택하면 남은 개수에서 조합을 만들면 됩니다.

만약 무게 2가 2개 있다면

2 * 2 = 4입니다. 

 

마지막으로 

3이상으로는 더이상 만들 수가 없습니다. 3외의 수, 4이상이 없기 때문입니다.

3 * 0 = 0

 

따라서 전체 방법의 수는 8입니다.

이를 그래도 소스코드로 옮겨 봅니다.

 

python

import sys
n, m = map(int,input().split())
arr = list(map(int, sys.stdin.readline().rstrip().split()))

count  = [0 for _ in range(m+1)] 
result = 0
for x in arr:
  count[x] += 1

for i in count:
  if i == 0:
    continue

  result += i * (n-i)
  n = n-i

print(result)

c++

#include <bits/stdc++.h>

using namespace std;

int main(){

  int n, m;
  int cnt=0;
  cin>>n>>m;
  int count[11] = {0}; 
  int result = 0;

  for(int i = 0; i < n; i++){
    int tmp;
    cin>> tmp;
    count[tmp]++;
  }
  for(int i = 0; i < m+1; i++){
    if(count[i] == 0) continue;
    result += count[i] * (n-count[i]);
    n = n - count[i];
    
  }
  cout<<result<<'\n';
}