문제 유형
여러 단위의 동전들이 주어져 있을때 거스름돈을
가장 적은 수의 동전으로 교환해주려면 어떻게 주면 되는가?
각 단위의 동전은 무한정 쓸 수 있다.
첫 번째 줄에는 동전의 종류개수 N(1<=N<=12)이 주어진다. 두 번째 줄에는 N개의 동전의 종류가 주어지고,
그 다음줄에 거슬러 줄 금액 M(1<=M<=500)이 주어진다.각 동전의 종류는 100원을 넘지 않는다.
필요자료구조
int n // (동전 갯수),
int m // (거슬러 줄 금액),
int dis[] // (n개 만큼 자연수 입력),
int ch[] // (중복 값은 탐색하지 않기 위한 check 배열)
int L // (현재 레벨),
BFS() 메서드 // 핵심 로직
핵심 문제 해석
-
가장 적은 수이기 때문에BFS를 사용해야겠다는 생각이 들었다. BFS는 보통최소 경우의 수를 구할 때 많이 쓰인다는 것이 생각났다.
-
현재 레벨 값에서 dis[j] 만큼 이동한 거리인
nx값이 거슬러 줄 동전 값m과 같다면 해당하는 레벨 값을 출력해줘야 한다.
핵심 코드
public int BFS(int[] dis){
int L = 0;
Queue<Integer> Q = new LinkedList<>();
Q.offer(0);
while(!Q.isEmpty()){
int len = Q.size();
for(int i = 0; i < len; i++){
int x = Q.poll();
for(int j = 0; j < dis.length; j++){
int nx = x+dis[j];
if(nx == m) return L+1;
if(ch[nx] == 0){
ch[nx] = 1;
Q.offer(nx);
}
}
}
L++;
}
return -1;
}
개선된 점
논리적으로 문제를 해결하려고 노력했다.
개발자에게 가장 중요한건 논리적인 문제해결 능력!
문제, 자료구조, 알고리즘, 코드 구현 모든 걸 논리적으로 해석하고 해결하려고 노력했다.
오답일 때 침착하게 코드 다시 읽어보고 디버깅 해보거나 코드 과정을 살펴보고 논리적으로 생각해봤다.
알고리즘 구현 부분은 확신을 갖고 있어서 자료구조 범위에 집중했다. 알고보니 두개의 문제가 있었다.
첫번 째 ch 배열의 크기였다. 문제에서 주어진대로 ch배열을 500 이상으로 설정해줘야 했다.
따라서, ch = new ch[501]로 초기화 시켰어야 했다.
두번 째. nx 값을 구하는 for문 size를 3으로 고정시켜버린 것이었다.
원래는 arr.size만큼 돌아야 arr 내부에 있는 값들의 경우를 모두 체크해볼 수 있는데 말이다.
두가지 사항을 수정하니 정답!!
피드백, 개선할 점
static int ch[]로 선언된 배열 값을 초기화 해주지 않으면 널포인트익셉션`이 발생한다는 사실을 몰랐다..
느낀점
개발자는 문제가 발생했을 때 논리적으로 해결하려는 자세가 가장 중요한 것 같다.
에러에 맞닥뜨려도 당황하지 않고,
"어떤 요소 때문에 이런 에러가 발생했을까?"
"내 로직, 알고리즘, 기능 구현, 프레임워크 .. 등
사이클은 어떻게 돌아가고 있지?
사이클 내에서 어느 부분에 구멍이 있는걸까?"
위와 같이 논리적으로 생각하면서 문제를 해결하려고 노력해야할 것 같다.!!
