그리디

이것이 코딩테스트다-314p

처음에 생각한 방법

5 입력받기

5만큼 자리 있는 배열 생성 후 값 받아오기

배열에 있는 값 오름차순으로 정렬

값으로 만들 수 있는 금액 만들고 정렬

count로 1씩 추가해가면서 만들 수 있는 금액과 비교

 

*문제점: 경우의 수를 다 생각해야 됨, 비교를 하면 for문을 또 돌려야 하는데 값으로 만들 수 있는 금액과 그 금액을 1씩 더해가며 비교하는 것은 효율적이지 않음.

 

다시 생각한 방법

5 입력받기

5만큼 값 받아오기

값 오름차순 정렬

작은 것부터 더해가면서 count를 다음 값과 비교

 

n=int(input()) // 몇 개의 동전이 있는지 입력 받기
number=list(map(int,input().split())) //리스트에 화폐 단위 받아오기
number.sort() // 화폐 단위 받아온 리스트 오름차순으로 정렬

count=1 //화폐 단위 받아온 것 더해가며 1부터 비교

for x in number: // number 리스트에서 순차적으로 하나씩 값 빼오기
    if count < x: // count가 x보다 작은 경우 for문 탈출
        break
    count= count+ x // count가 x보다 같거나 큰 경우 count에 x값 더하면서 갱신

print(count) // count 출력

파이썬 공부 참고 블로그

https://blog.naver.com/wpghks7/221584113312

[파이썬으로 시작하는 삼성 SW역량테스트] - 1. 입력받기

import java.util.*;

public class Greedy {

	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int[] number = new int[n];
		for(int i=0;i<number.length;i++)
			number[i]=sc.nextInt();
		
		Arrays.sort(number);
		
		int count=1;
		
		for(int j=0;j<n;j++) {
			if(count<number[j]) break;
			count+=number[j];
		}
		System.out.println(count);
	}
}

 

이것이 코딩테스트다-315p

 

같은 무게의 공이 여러 개 있을 수 있지만, 서로 다른 공으로 간주

(1,1), (2,2) 같은 것끼리 묶을 수 없음

(1,2), (2,1) 다른 걸로 보지 않음

 

생각한 방법

볼링공의 개수와 볼링공의 최대 무게 숫자 2개 받기

볼링공의 무게 list로 받기

for문을 돌면서 현재 공의 무게와 다른 무게면 count 1씩 올려주기

 

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

count=0
for i in range(0,len(number)):
    for j in range(i,len(number)):
        if number[i] != number[j]:
            count+=1

print(count)

 

답안

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

array=[0] *11 // 1부터 10까지 무게를 담을 수 있는 리스트

for x in number:
    array[x] += 1 // 각 무게의 해당하는 볼링공의 개수 카운트

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

print(result)

무게마다 볼링공이 몇 개 있는지 계산

카운트 된 배열을 각 무게에 대해서 

볼링공의 개수에서 무게가 i인 볼링공의 개수를 빼주고

A의 경우의 수를 뺀 n을 다음 사람이 선택하는 경우의 수와 곱해주는 계산을 반복