Dynamic Programming3 [BOJ] 백준 14916번 - 거스름돈(with Java) 알고리즘 문제에서 궁극적으로 구하고자 하는 답은 거스름돈 N이 주어질 때, 거슬러주는 동전의 최소 개수이다. 따라서 다른 DP 문제들과 마찬가지로 N 이하에서의 DP 값을 모두 알아야만 한다. 이 문제에서 알아둬야할 부분은 '손님이 2원짜리와 5원짜리로만 거스름돈을 달라고 한다' 이다. 다시 말해서 2원 또는 5원으로 거슬러줄 수 없는 경우가 존재한다는 뜻이며, 이 경우에는 -1을 넣어줘야만 한다. dp[0]을 구해보자. dp[0]은 거스름돈 0이 주어질 때, 거슬러주는 동전의 최소 개수이다. 하지만 거스름돈이 0이라면 거슬러줄 필요가 없으므로 거슬러주는 동전의 최소 개수는 0, 즉 dp[0] = 0이다. dp[1]은 거스름돈 1이 주어질 때, 거슬러주는 동전의 최소 개수이다. 거스름돈이 1인 경우에는 .. 2021. 12. 5. [BOJ] 백준 2293번 - 동전 1(with Java) 알고리즘 지난번에 풀었던 [BOJ] 백준 11047번 - 동전 0 문제와는 다르게 욕심쟁이 알고리즘이 아닌 '동적계획법'을 사용해야만 문제가 풀린다. 우선 K번째까지의 경우의 수를 구하는 것이 목표이므로 DP 배열의 크기를 K+1로 잡아주고 dp[0]을 1로 초기화해준다. 0이 아닌 1로 초기화를 해주는 이유는 동전을 아예 사용하지 않는 경우도 경우의 수에 포함된다고 봐야하기 때문이다. 다음으로 이중 for문을 통해서 알고리즘이 수행된다. dp[j]는 첫번째부터 j번째까지의 동전을 사용했을 때 합이 K원이 되도록 만드는 경우의 수이다. 예를 들어서, 동전 각각의 가치가 2원 3원 5원이고 가치의 합이 10원이라고 해보자. 첫번째로 dp[j]는 2원짜리 동전으로 2원부터 10원까지 만들 수 있는 경우의 수.. 2021. 8. 2. [BOJ] 백준 1904번 - 01타일(with Java) 알고리즘 N=1부터 N=8까지의 각각의 경우에 대해서 만들 수 있는 가짓수를 계산해보면 아래와 같이 도출된다. 결과를 보게 되면 3번째항부터는 이전 항과 그 이전 항을 더해서 만들어지는 피보나치 수열임을 알 수 있다. 따라서 N=1, N=2일 때는 정답을 각각 1과 2로 출력해주고, N=3 이상부터는 i-2번째와 i-1번째 항을 더해서 i번째 항을 구하면 된다. N은 최대 백만까지 가능하므로 15746으로 나눠줘야만 하는데, 정답을 도출할 때 나눠주게 되면 이미 오버플로우가 발생한 상태로 결과가 나오게 된다. 이를 방지하기 위해서는 i-2번째 항과 i-1번째 항을 합해준 후에 15746을 나눈 값으로 i번째 항을 구해주면 문제가 해결된다. 소스코드 문제링크 1904번: 01타일 지원이에게 2진 수열을 가.. 2021. 7. 19. 이전 1 다음
