partitioned
-
[문제해결을 위한 창의적 알고리즘] partitioned 2 (고급 p.68)알고리즘 2016. 12. 30. 17:44
앞선 포스트에서는 본 문제에 대한 보다 직관적인 풀이를 적었습니다. 그러나 책의 해설이 보여주는 풀이도 나름 의미가 있고 이해하고 있는 편이 좋을 것 같다는 생각이 들어 여기에 적어보자 합니다. 책의 풀이를 보면 f(n, k) = k이하의 자연 수 합으로 n을 만들 수 있는 경우의 수 라고 되어 있는데, 예제 입력의 경우를 살펴보면 n=5일때, 5이하의 자연수 합으로 5를 만들 수 있는 경우의 수를 구하는 함수라고 보면 될 것 같습니다. (실제 출력은 경우의 수가 아니라 각 경우를 출력해야 한다는 점은 주의해야 겠지요.) 코드를 살펴 보겠습니다. import java.util.Scanner; public class PartitionedSol70 { // 문제에서 30이하의 수라고 했으므로 30개의 정수 ..
-
[문제해결을 위한 창의적 알고리즘] partitioned (고급 p.68)알고리즘 2016. 12. 23. 17:57
이 문제의 해설은 굉장히 직관적이지가 않아 내 나름대로의 방법으로 풀어 보았다. 그림 설명과 결과값 출력이 조금 헛갈리게 설명되어 있으나, 출력 결과 값을 보면 주어진 n을 분할해서 내림차순 형태의 배열을 출력한다고 간단히 이해한 후 문제를 접근하는 편이 훨씬 낫지 않나 싶다. import java.util.Scanner; public class Partitioned { public static int n; //n은 30이하의 자연수라고 제한되어 ㅇ public static int[] arr = new int[30]; // f는 k개의 정사각형 종이를 id번째의 배열에 몇개를 놓을 수 있는지를 계산 public static void f(int k, int id){ // k가 0, 즉 정사각형이 다 떨어졌..