문제

위의 문제에서 수를 입력했을 때, 입력한 값이 3과 5로 구성이 가능해야하며, 그 중에서도 몫의 합이 제일 작은 수가 도출되어야 한다.

ex) 18 = 3 x "6" 이지만, (5 x "3") + (3 x "1")로도 나타낼 수 있기 때문에, 6보다 작은수 4가 출력되어야 한다.

위의 문제와 같은 경우 풀수있는 많은 방법들이 존재하지만, 나는 5와 3으로 나누는 수의 규칙성을 이용하여 문제를 해결하였다.

나의 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		// 사탕봉지 갯수 입력
		int n = Integer.parseInt(br.readLine());
		// 봉지 갯수 카운트
		int cnt = 0;

		if ((n % 5) == 0) { // 5키로로 나눌 수 있으면 5키로에 모두 담기
			cnt = n / 5;
		} else if ((n % 5) == 1) { // 5의 배수 + 1 이라면 5키로봉지 하나 빼고 3로봉지 2개 추가
			cnt = n / 5 + 1;
		} else if ((n % 5) == 2 && n >= 12) { // n을 5로 나누었을때 2가 남는다면 (2와 7 제외)
			cnt = n / 5 + 2;
		} else if ((n % 5) == 3) { // 5로 나눈 나머지가 3이라면
			cnt = n / 5 + 1;
		} else if ((n % 5) == 4 && n != 4) {// n을 5로 나누었을때 나머지가 4가 남는다면 (4 제외)
			cnt = n / 5 + 2;
		} else { // 그 외의 모든 경우는 -1로 처리.
			cnt = -1;
		}
		System.out.println(cnt); // 결과값 출력
	}
}

첫 문제풀이, 그리고 개선해야 할 점.

솔직히 첫 알고리즘 풀이라 많이 막혔다. 접근 방식은 비슷했지만, 코드를 구성하는 부분에서 중간 부분부터 어떤 방식으로 구성을 해주어야 할지 막막하였다.

반례가 될 수 있는 경우의 수에 대해서 너무 신경을 쓰다보니 진행이 더뎌져 다른 사람들의 풀이를 참고로 하여 문제를 해결하였다.

처음에는 그저 5의 배수인 경우, 3의 배수인 경우, 5와 3의 최소공배수인 경우 등등 다양하게 접근을 시도해보았지만,그리디 알고리즘 문제에서는 "매 순간마다 좀 더 좋은 방법으로 접근"하려는 것이 궁긍적인 목적이기에 접근법에서부터 일반적인 문제를 풀듯이 접근하면 안된다는것을 깨닫았다.

다음 문제부터는 최대한 신경을 써서 문제를 해결해보아야 할 것 같다.