11월 2주차 Ec.crew (그리디 알고리즘, 우선순위 큐)

11047번: 동전 0 (acmicpc.net)

11047번: 동전 0

C언어로 코딩, 그리디 알고리즘 기본문제!

//백준 11047번 : 동전 0
#include <stdio.h>

int main() {
    int N, K;
    int coin[10];
    int cnt =0; // cnt는 동전의 개수

    scanf("%d %d", &N, &K);
    for(int i=0; i<N; i++)
        scanf("%d", &coin[i]);

    for(int i = N-1; i>=0; i--) {
        if (K >= coin[i]) { //입력받은 총액 K가 지정된 단위 N값보다 크면
            cnt += K / coin[i]; //cnt 증가
            K %= coin[i]; //K는 coin[i]으로 나눈 값으로 갱신
        }
    }
    printf("%d", cnt);
    return 0;
}

1715번: 카드 정렬하기 (acmicpc.net)

1715번: 카드 정렬하기

자바로 코딩, 우선순위 큐 사용

(C언어로 코딩하면 우선순위 큐도 일일이 코드를 다 짜야하는데 자바로 코딩하면 복잡한 프로그래밍 없이 바로 갖다 쓸 수 있어서 자바로 풀었다)

 

<풀이법>

현재 가지고 있는 카드뭉치 중 가장 작은 카드 2개를 뽑아 새로운 뭉치 만들기

여기서 카드뭉치는 새롭게 합쳐져서 만들어진 뭉치까지 포함

1) pq에 모든 카드의 개수 넣기

2) 작은 것 2개를 뽑아서 비교횟수를 answer에 저장

3) 새로 만들어진 뭉치를 pq에 다시 넣기

4) 뭉치가 하나만 남을 때까지 반복하고 answer 출력

import java.io.BufferedReader; //BufferedReader는 문자 버퍼 스트림을 구현
import java.io.InputStreamReader; //InputStreamReader는 스트림에 입력되는 바이트 데이터를 문자집합을 통해 문자로 변환
import java.util.PriorityQueue; //PriorityQueue는 우선순위 큐

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PriorityQueue<Integer> pq = new PriorityQueue<Integer>(); //우선순위 큐 pq를 정의
		int N = Integer.parseInt(br.readLine()); //입력받은 값 N을 Wrapper클래스로 정수를 Integer객체로 만듦. 

		for (int i = 0; i < N; i++)
			pq.add(Integer.parseInt(br.readLine())); //입력받은 모든 정수값을 pq에 삽입
		int answer = 0; //answer값을 0으로 초기화
		while (pq.size() != 1) { //pq의 크기가 1이 아닐 때까지 계속 반복
			int cnt = pq.poll() + pq.poll(); //우선순위 큐 pq에서 가장 작은 값 두 개를 뽑아 더해서 cnt에 넣기 
			pq.add(cnt); //새로 만든 cnt를 다시 우선순위 큐 pq에 넣기
			answer += cnt; //answer에 cnt 더해주기
		}
		System.out.println(answer); //answer 출력
	}

}