알고리즘 스터디 - 3주차 2

14916

• 알고리즘 : 그리드 알고리즘
• 난이도 : 실버5

문제

14916

접근

• 거스름돈 문제는 대부분 그리드 알고리즘이다.
  • 그리드 알고리즘이란 가장 큰 수부터 먹고 그 다음 큰 수가 먹는 경우다.
    • 15원이 있으면 가장 큰 수인 5원 부터 계산... 3개
    • 13원이 있으면 5원 부터 2개... 2원 1개 불가 시 다시 5원 1개 .. 2원 4개 --> 총 5개

가정

• 거스름돈은 무조건 돌려줘야한다.
• 그리드 알고리즘으로 푼다.

풀어보기

package org.example;

import java.util.Scanner;

public class Main {
	public static void main(String[] args) 	{
		Scanner scanner = new Scanner(System.in);

		int returnMoney = scanner.nextInt();
		System.out.println(greedy(returnMoney));

	}
	public static int greedy(int money){
		if(money == 1 || money == 3) return -1; // 처음 부터 왼쪽 값이라면 -1 리턴
		int minCount = money / 2; // 2로 나눈 값이 가장 크다.
		for(int i =0; i  < money / 5 + 1; i++ ){ // 5의 갯수를 전부 구한다ㅣ.
			int returnCount = 0;
			int origin = money - 5 * i ; // 5의 갯수를 0일 경우부터 최대인 경우를 구한다.
			if(origin == 3 || origin == 1) continue; // 5를 빼고 나면 3과 1은 거른다.
			returnCount  = i; // 5의 갯수를 먼저 시작
			if(origin % 2 == 0) { // 2의 배수라면 2로 나눈 값이 동전 갯수
				returnCount += origin / 2; // 2의 동전 갯수를 더함.
			}
			if(origin % 2 != 0) continue; // 2로 안떨어지면 5의 갯수를 줄이러 이동
			if(returnCount == 0) continue; // 여기까지 왔는데 아무 값이 없으면 이동
			if(minCount > returnCount) { // 최소의 값을 구하기 위한 조건식
				minCount = returnCount;
			}
		}
		return minCount; // 최소값을 리턴한다.
	}

}

시행착오

• 그리디 문제 중 가장 시행 착오를 많이 했던 거 같다.
  • 오히려 더 큰 수가 나오면 처리하기 쉽지만 5와 2라는 수로 인해 헷갈렸던 것 같다.
  • 전부 2로 나눈 값들이 가장 거스름돈 갯수가 많을 것이다.
  • 5가 없는 경우 부터 시작하여 5의 갯수를 for문으로 계산하였다
  • 비효율적이였지만 정확했다.
  • 1과 3인 경우를 추가하지 않았다.

참고자료