devbelly

문제 www.acmicpc.net/problem/2720 알고리즘 구현 풀이 이 문제는 제가 파이썬 구현 연습을 위해 풀다가 마주한 문제입니다. 구현 외에 짚고 넘어갈 점이 있어 포스팅하겠습니다. 저는 브론즈3이라는 점에서 구현 외에 별 다른 부분은 신경쓰지 않고 풀었던 문제입니다. 하지만 조금 생각해본다면 수상한 점을 발견할 수 있습니다. 문제 내용은 거슬러 주는 동전의 갯수를 최소화 하는 문제입니다. 그리디 또는 다이나믹 프로그래밍을 다룰 때 많이 등장하는 주제중 하나입니다. 그리디로 문제를 해결하려고 동전의 값을 보았지만 거슬러 줄 수 있는 동전의 값은 25원 10원 5원 1원 입니다. 동전들 끼리 배수관계를 만족하지 못하므로 (25원과 10원) 다이나믹 프로그래밍을 이용해 해결하자! 라고 생각할 ..

문제 https://www.acmicpc.net/problem/1493 알고리즘 분할정복, 그리디 풀이 박스를 큐브로 채워나갈 때, 필요로 하는 큐브의 갯수를 최소화 하는 문제입니다. 단 큐브의 사이즈는 2의 제곱형태로만 주어지는 제약이 있습니다. 큐브길이가 2의 제곱형태로만 주어지는 점부터 살펴봅시다. 만약 이렇지 않았다면, 모든 큐브를 일일히 넣어보는 완전탐색을 해야합니다. 하지만 모든 길이가 배수와 약수 관계를 유지할 때, 무조건 큰 길이부터 넣는 그리디한 전략을 사용할 수 있습니다. 큰 길이의 큐브를 넣어야만 갯수를 최소화 할 수 있고, 예를들어 4x4x4큐브를 사용했다면 굳이 2x2x2큐브들로 그 자리를 대체할 이유가 없죠. 살펴보아야 할 점 중 또 한가지는 큐브길이는 제곱형태로 주어지지만 박스..