간지나제의 기술블로그

programmers.co.kr/learn/courses/30/lessons/12907 코딩테스트 연습 - 거스름돈 Finn은 편의점에서 야간 아르바이트를 하고 있습니다. 야간에 손님이 너무 없어 심심한 Finn은 손님들께 거스름돈을 n 원을 줄 때 방법의 경우의 수를 구하기로 하였습니다. 예를 들어서 손님께 5 programmers.co.kr 규칙찾기도 굉장히 어렵고 그것을 코드로 구현할 때도 2차원 배열이 아닌 1차원 배열로 중첩해서 푸는 방식이 인상적인 문제였다. 어떻게 푸는지 몰라서 블로그를 많이 참고했고 이해하기도 어려웠다. 2차원 배열로 했을 때 행렬을 만들게 되면 기본적으로 O(N^2)이상이 되기 때문에 시간초과가 날 것이다. 따라서, 아래와 같이 푼다면 이중 for문이지만 money.len..

dp를 이해하는데 가장 기본이 되면서 중요한 문제가 아닐까 싶다. dp는 기본적으로 bottom-up 방식을 선호하는데 차례차례 적다보면 규칙이 보이기 때문이다. 이게 쉽게 찾아지냐 안 찾아지냐의 차이에 따라서 dp의 난이도가 결정되는 것 같다. 이 문제 같은 경우는 n-1과 n-2를 통해서 n을 찾는 문제이다. n-1 경우에 한 개를 더 붙인 경우, n-2 경우에 두 개를 더 붙인 경우라고 가정하고 풀면 n의 경우가 나오게 되는 걸 알 수 있다. 실제로 n=4의 경우의 수를 그려보고 n=3과 n=2의 경우를 그려보고 막대기를 갖다댄다면 4의 경우수만큼 그릴 수 있다. import java.util.*; import java.io.*; public class Main { public static void..

dp는 규칙을 찾아서 간결하게 푸는 문제인데 정리능력이 부족한건지 집중력 부족인지 잘 해결하지 못했다. 다른 블로그 참조해서 보려고 해도 이해가 전혀 가지 않아서 찾고 찾다가 아주 쉽게 풀어놓은 블로그가 있어서 그걸 보고 겨우 이해했다. 간결하게 테이블로 규칙을 찾아서 하나씩 해보는 연습이 필요할듯 싶다. 기초문제이지만 멘탈을 엉망진창으로 만들 수 있다는 걸 보여준 사례... public static final int MOD = 1000000000; static int N, K; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System..