BaekJoon - 11047
동전 0
https://www.acmicpc.net/problem/11047
11047번: 동전 0
첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)
처음 생각
그리디 알고리즘 문제로 내가 그리디 하면 떠오르는 것은 최소한의 아이디어를 떠올리고 정당한지 따지는 것이기에 큰 동전부터 넣는 것이 맞다고 생각했다.
증명
Money = coin1 * n1 + coin2 * n2 + coin3 * n3 ...
총 숫자 = n1 + n2 + ...
이런 방식으로 표현한다고 생각한다면 필요한 동전의 숫자는 coin이 클수록 작아진다.
코딩
사실 문제는 굉장히 간단하기에 마땅히 코딩을 할 이유가 없을 정도지만 중간에 내가 다른 방향으로 빠져서 적어보자 한다.
일단 문제에서는 동전의 배열의 크기와 각 배열에 들어갈 동전의 단위를 전부 준다. 그런데 나는 1 5 10 50 같이 우리의 실생활의 화폐 단위처럼 자동으로 생성해서 배열을 만들어야지 생각했다. 따라서 숫자만 넣어준다면 for문을 돌려서 자동으로 배열이 만들어지도록 했다.
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int coinNum = scanner.nextInt();
int[] set = new int[coinNum];
int a = 1;
for (int i = 0; i < coinNum; i++) {
if (i == 0) {
set[i] = a;
} else if (i % 2 == 0) {
set[i] = set[i - 1] * 5;
} else {
set[i] = set[i - 1] * 2;
}
}
int count = 0;
int money = scanner.nextInt();
for (int i = coinNum - 1; i >= 0; i--) {
while (set[i] <= money) {
money -= set[i];
count++;
}
}
System.out.println(count);
}
}물론 잘못된 방식이기에 '틀렸습니다'를 받았고 바로 내가 뭘 잘못했는지는 알았다. 그런데 내가 여기서 생각한 것은 안의 함수를 메서드 처리해보고 싶다는 생각이 들었다. 사실 이게 글을 남기는 이유다.
이제까지 코테 문제를 풀 때는 굳이 메서드를 따로 빼서 만들어야 하나 생각을 했다. 그런데 객체지향 책도 읽고 하니까 그냥 이런 방식으로 코드를 작성하면 큰 죄를 저지르는 기분이 많이 든다. 그래서 물론 정답과는 다르지만 메서드로 만들어서 바깥으로 빼는 방식으로 다시 만들어 보았다.(물론 틀렸다)
public class Main2 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int coinNum = scanner.nextInt();
int[] set = setCoinArray(coinNum);
int count = 0;
int money = scanner.nextInt();
for (int i = coinNum - 1; i >= 0; i--) {
while (set[i] <= money) {
money -= set[i];
count++;
}
}
System.out.println(count);
}
public static int[] setCoinArray(int coinNum) {
if (coinNum <= 0) return null;
int[] array = new int[coinNum];
int a = 1;
for (int i = 0; i < coinNum; i++) {
if (i == 0) {
array[i] = a;
} else if (i % 2 == 0) {
array[i] = array[i - 1] * 5;
} else {
array[i] = array[i - 1] * 2;
}
}
return array;
}
}이런 방식으로 메서드를 빼는 과정에서 많은 생각을 하게 되었다.
- 메서드의 이름은 무엇으로 해야 하지?
처음에는 array를 받으니까 array로 했다가 무언가 잘못되었다 생각하고는 동사로 시작하는 지금의 방식으로 바꾸었다. - 파라미터로 인트를 받는 게 맞을까?
이것도 고민한 부분인데 지금은 int를 받고 배열을 메서드에서 생성하는 과정을 가지고 있다. 그런데 만약 int[]의 배열을 파라미터로 받고 인자로 돌려주는 방식은 어떨까 라는 생각을 했었다. 사실 이 부분은 지금도 잘 모르겠기에 내일 찾아볼 예정이다.
실제 풀이와 답
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int coinNum = scanner.nextInt();
int[] set = new int[coinNum];
int count = 0;
int money = scanner.nextInt();
for (int i = 0; i < coinNum; i++) {
set[i] = scanner.nextInt();
}
for (int i = coinNum - 1; i >= 0; i--) {
while (set[i] <= money) {
money -= set[i];
count++;
}
}
System.out.println(count);
}
}for문을 열심히 돌면서 배열을 입력받으면 나머지는 같다. 그리디 알고리즘은 구현 부분이나 최소한의 아이디어 2가지가 중요한 것 같다.
생각
이전에는 코테 문제를 그냥 main() 메서드에 꾸겨넣는 일을 많이 했었는데 책도 많이 보고 나름 메서드들을 많이 만들어 보니 생각이 많이 바뀌게 되었다. 자바를 사용하는 만큼 객체지향적인 방식으로 코딩을 하는 버릇을 들이는 것이 중요하다고 평소에 생각을 하게 되었기에 이번에도 그렇게 한번 해보았다. 그리고 굉장히 간단한 메서드인데 내가 스스로 만드는 메서드는 뭔가 신경 쓸 부분도 많고 이게 맞나?라는 생각이 많이 든다. 이런 부분을 채워 나가며 내 실력을 키워야겠다.
