Baekjoon - 17626

문제

Solved.ac Class3++

1차시도

public class Main {
	private static int[] squareData;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int count = Integer.MAX_VALUE;
		int number = Integer.parseInt(br.readLine());
		squareData = new int[50000 + 1];

		int temp = 1;
		while (temp * temp <= number) {
			squareData[temp] = temp * temp;
			temp++;
		}
		temp--;

		for (int i = temp; i > 0; i--) {
			int solve = solve(i, number, 1);
			if (solve < count) {
				count = solve;
			}
		}

		System.out.println(count);
	}

	private static int solve(int pointNow, int numberNow, int count) {
		int minus = numberNow - squareData[pointNow];
		int returnValue = Integer.MAX_VALUE;

		if (minus == 0) {
			return count;
		}
		if (pointNow > 0) {
			if (minus > 0) {
				returnValue = solve(--pointNow, minus, count + 1);
			} else {
				returnValue = solve(--pointNow, numberNow, count);
			}
		}
		return returnValue;
	}

}

틀렸습니다

2차시도

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int number = Integer.parseInt(br.readLine());
		int[] data = new int[50000 + 1];

		data[1] = 1;

		for (int i = 2; i <= number; i++) {
			int min = Integer.MAX_VALUE;
			for (int j = 1; j * j <= i; j++) {
				min = Math.min(min, data[i - j * j]);
			}
			data[i] = min + 1;
		}
		System.out.println(data[number]);
	}
}

위 풀이식 대로는 해결이 될것 같지 않아 검색해보았다.
DP를 이용한 풀이법인데
i번째 데이터를 찾으려면 i보다 작은 제곱이 되는수(ex. i가 10일때 제곱수는 $1^2$, $2^2$, $3^2$)들 중
가장 작은것을 찾는다. 거기다가 1을 더하면 현재 위치의 최소 제곱수의 개수가 된다.
(전에거 + $j^n$을 해서 현재 숫자를 만들겠다는 뜻)

성공

ToKotlin

fun main() {
    val number = readln().toInt()
    val data = IntArray(50000 + 1)

    data[1] = 1

    for (i in 2..number) {
        var min: Int = Int.MAX_VALUE
        var j = 1
        while (j * j <= i) {
            min = min(min, data[i - j * j])
            j++
        }
        data[i] = min + 1
    }
    print(data[number])
}

성공