고양이 두 잔

문제 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다. 상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면 더 적은 개수의 봉지를 배달할 수 있다. 상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000) 출력 상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확..

문제 지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다. 체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다. 보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8..

완전 탐색이란 컴퓨터의 성능을 믿고 모든 경우의 수를 다 체크하는 방법이다. 상대적으로 구현이 간단하고, 해가 존재한다면 반드시 찾을 수 있는 방법이기도 하다. 예를 들어 숫자 4자리로 구성된 자물쇠의 암호를 푼다면, '0000'부터 '9999'까지 다 넣어보는 방식이다. 당연하게도 최적의 솔루션을 제공해주지 않으며, 때문에 다음 두 상황에 주로 쓰인다. 적용 가능한 다른 알고리즘이 없을 때 복수의 솔루션을 확인해야 할 때 예를 들어 책 한 권이 주어지고 그 책에서 '고양이'라는 단어를 찾아야 한다고 가정해보자. 책은 당연하게도 단어들이 정렬되어 있지 않으므로 처음부터 끝까지 단어를 비교하는 수밖에 없다. 이럴 때 사용되는 것이 완전 탐색 알고리즘이며, 이 경우 시간 복잡도는 O(n)이다. 계속해서 완전..