백준 - 동전 0(그리디 알고리즘), 파이썬 & C

https://www.acmicpc.net/problem/11047

11047번: 동전 0

 

[파이썬]

N, K = map(int, input().split())
	
coins = []
count = 0
for _ in range(N):
	coins.append( int( input() ) )

idx = len( coins ) - 1
	
while K > 0:

	if ( K - coins[idx] ) >= 0 :
		count += 1
		K -= coins[idx]
		idx = len(coins) - 1
		continue
		
	idx -= 1

		
print( count )

그냥 실행시키면 시간 오류가 뜨기 때문에 PyPy3로 실행시켜보니 잘 된다. 

 

 

[C]

#include <stdio.h>

int main(void)
{
	int N, K, arr[101];
	
	scanf("%d %d", &N, &K);
	
	int i=0;
	
	for(i=0; i<N; i++){
		scanf("%d", &arr[i]);
	}
	
	int count = 0;
	for(i=N-1; i>=0; i--){
		if( K / arr[i] >= 0 ){
			count += K / arr[i];
			K %= arr[i];
		}
	}
	
	printf("%d", count);
	
	return 0;
}

얘는 더 효율적으로 나머지와 몫으로 구하는 방법