백준 2839번: 설탕 배달

문제 설명

• 5와3을 적절해 더해서 N을 만들 수 있는지, 만들 수 있다면 5와 3을 가장 적게 사용하는 방법이 무엇인지를 구하는 문제입니다.

접근법

• 배낭문제와 같이 생각하고 풀 수 있습니다.
  • 3보다 5를 넣는 게 유리하기 때문에 5를 최대한 많이 집어넣습니다.
  • 5를 최대한 많이 넣고 남은 공간(rest)이 3으로 나누어 떨어진다면 N을 만들 수 있다는 뜻입니다.
  • rest가 3으로 나누어떨어지지 않는다면 5를 하나 뺍니다. 5를 빼고 남은 공간이 3으로 나누어 떨어지는지를 확인합니다.
  • 5를 전부 빼는 경우까지 확인해 봅니다. 5를 전부 빼도 공간이 3으로 나누어떨어지지 않는다면 해당 수 N은 3과5로 만들 수 없다는 뜻입니다.

정답

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int cnt = 0;
		cnt += N/5; //가방을 5키로짜리로 채움
		int rest =N%5; //가방에 남은 공간
		while (rest<=N) {//5를 전부 뺄때까지 반복합니다.
			if(rest%3 == 0) {
				cnt+=(rest)/3;
				break;
			}else {
				rest +=5;
				cnt--;
			}
		}
        
		if(rest>N) {//입력값이 4인 경우 9>4가 됩니다.
			System.out.println(-1);
		}else {			
			System.out.println(cnt);
		}
	}
}

//1주일 뒤에 다시한번 풀어봤습니다.
import java.io.*;

class Main {
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		boolean token = true;

		int rest = N%5;
        //i는 뺄 설탕의 개수입니다 0개부터 시작해 N/5까지 5kg설탕을 빼봅니다.
		for (int i = 0; i <= (int)N/5; i++) { 
			if((rest+5*i)%3 == 0) { // rest+5*i는 i개의 5kg설탕을 뺀 뒤 채워야하는 무게입니다.
            	// (N/5)-i는 5kg설탕의 개수, (rest+5*i)/3은 3kg설탕의 개수입니다.
				System.out.println((int)(N/5)-i + (int)(rest+5*i)/3);
                // -1출력을 방지하기 위한 token입니다.
				token = false;
				break;
			}
		}

		if(token) {
			System.out.println(-1);			
		}
	}
	

}

기타

• 처음에 5또는 3을 한 묶음 만들었을 때 나머지 수들도 나누어 떨어지면 유효하다고 생각했습니다.(잘못된 접근예시)
  • 
  • 정수론으로 접근하면 어려워지는것 같습니다.

• 문제를 풀 때 딱 맞아떨어지는 방식을 찾으려고 한다. 이 문제나 완전탐색처럼 직접 시행하면서 찾는 문제를 잘 못맞춘다. (이런 방식으로 접근해봐야겠다는 생각을 아직까지 잘 못한다.)