KOMAS

https://www.acmicpc.net/problem/1699

다이내믹 프로그래밍을 이용한 문제다.

1, 4, 9, 16.. 과 같은 제곱수를 활용하여 주어진 수 N을 최소한의 개수로 구성하는 것이 답이다.

최적의 값을 idx에 기억해두는 바텀업 방식으로 이중 for문을 사용했다.

해당 문제에서 최적의 값은 최소한의 연산 횟수다.

DP 테이블 초기화

먼저 dp 테이블을 idx는 숫자, value는 최소 연산 횟수로 사용된다.

각 제곱수 idx 는 1로 만들어 주고,

나머지는 min을 알아내야 하니 충분히 큰 값으로 채워놓는다.

첫 for문은 1부터 100_000까지 차례대로 최소 연산을 구하게 된다.

두번째 for문은 최소 연산을 구하기 위해 

j의 제곱이 i 기준 수 보다 크면 의미가 없으므로 continue 하고,

j의 제곱이 i 기준 수보다 작다면 몫과 나머지를 구해서 

나머지 값에 해당되는 idx에 해당되는 값 + 현재 몫으로 이전에 구해둔 값과 비교해서 최적의 값을 구할 수 있다.

바텀업 방식이니

나머지값에 해당되는 idx는 현재 i 위치보다 이전 값일 것이고, 

최적의 값이라는 것이 보장되고 사용하기 무리가 없다.

예전에 풀었던 1463번 1로 만들기 문제와 비슷하다.

코드

import java.io.*;
import java.math.BigInteger; // subtract , multiply, add, mod
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        int number = Integer.parseInt(br.readLine());

        // dp 초기화
        int[] dp = new int[100001];
        Arrays.fill(dp, 1000_000);
        dp[0] = 0;
        for(int i = 1 ; i * i<dp.length; i++){
            int powNumber = i * i;
            dp[powNumber] = 1;
        }

        // 1부터 100_000 까지 min을 채워나가기
        for(int i = 1 ; i<dp.length; i++){
            for(int j = 325; j >= 1; j--){
                int jNumber = (int)Math.pow(j, 2);

                if(jNumber > i) // 기준숫자보다 제곱이 커지면 의미가 없으니 넘김
                    continue;

                int divide = i / jNumber;
                int rest = i % jNumber;

                dp[i] = Math.min(dp[i], dp[rest] + divide);
            }
        }
        System.out.println(dp[number]);
    }
}

https://www.acmicpc.net/problem/15649

• 문제 이해
• 해결 방법
• 구현

문제 이해

먼저 N, M 두 숫자를 입력받는다. N은 1부터 N까지를 의미한다.

M은 출력 자릿수를 결정한다.

이 문제 N과 M (1)은 M 자릿수를 출력하며 1부터 N까지 중복 없이 출력하는 경우이다. 이 문제의 출력은 결국 순열을 의미한다.

N과 M 문제 시리즈 같은 경우는 순열, 중복순열, 조합, 중복 조합 등을 백트래킹을 이용해서 구현하는 방법을 훈련할 수 있다.

이 문제는 백트래킹을 몰랐다면 풀기 어려웠을 것 같다.

해결 방법

우선 재귀 함수를 이용하여 자리수를 하나씩 채워간다. 즉 재귀가 될 때마다 자릿수가 다음 자릿수로 넘어간다.

재귀의 인자로 자리수 번호를 0부터 시작하여 앞부터 채워나간다.

재귀가 진행될 때 마다 0 1 2 3 4 자릿수를 채워나간다. 자릿수를 넘치면 종료 조건이 된다. 

재귀 함수 내에서 반복문으로 1부터 N까지 진행하게 해 두고 반복 문안에 재귀 함수를 만들어두면 1 -> 1- > 1 ->....로 재귀 함수가 호출이 되고, 자릿수가 넘쳐서 종료 조건을 만나면 이전 재귀함수로 돌아와 1 -> 1 -> 1 -> 2 이런 식으로 다음 반복을 진행하게 되어 모든 경우의 수를 출력할 수 있을 것이다.

하지만 이 방법은 중복순열이 되므로 중복된 숫자를 출력하지 않게 하도록 방문처리를 해주어야 했다.

중복된 숫자를 출력하지 않도록 하는 중복처리는 boolean[] 배열을 이용해서 재귀 함수 호출 이전에 for문 안에서

방문하지 않았다면 방문 처리한 후 다음 재귀 함수를 호출해서 다음 재귀로 넘어가도록 하였다.

이렇게 되면 다음 재귀 함수에서 1부터 사용하려 하겠지만 방문처리가 되었다면 다음 숫자의 반복으로 진행이 되므로

중복된 숫자가 출력되지 않도록 처리를 해줄 수 있다.

재귀 함수가 종료조건을 만나면 이전 재귀 함수 위치로 돌아오고 해당 수의 방문처리를 해제해준다.

여기서 이런식으로 방문 처리를 해제해주면 어차피 다음 반복문은 +1 이므로 해당 자릿수에서는 같은 숫자를 출력하지 않을 것이다.

* 예를들어 1234 출력 후 1234가 다시 안 되는 이유는 다음 반복을 진행하므로 1235가 된다. 

결국 방문처리 해제는 해당 자리수를 위한 것이 아니라 반복문이 전부 종료되면 이전 자릿수의 재귀 함수 호출로 돌아갈 것이므로 그곳에서

해당 숫자를 사용하기 위해 해체해주는 것이다.

마지막으로 재귀가 진행될때마다 자릿수에 중복 없이 저장될 숫자를 저장할 배열을 자리수 크기만큼 만들어둔다.

재귀 함수의 종료 조건은 자릿수가 넘치면 종료된다.

배열은 index가 0부터 시작하므로 자릿수가 넘치는 경우는 각 숫자를 저장한 배열의 index가 M 자릿수가 될 때이다.

재귀 함수를 종료시키며 이때 숫자를 저장해두었던 배열을 출력한다.

구현