200925 금 [BOJ] 1699

BOJ 1699 DP

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {	

    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    	
    	int N = Integer.parseInt(br.readLine());
    	int[] cache = new int[N+1];
    	
    	
    	cache[1] = 1;
    	
    	for(int i=2;i<=N;i++) {
    		cache[i] =i;
    		for(int j=1;j*j<=i;j++) {
    			cache[i] = Math.min(cache[i-(j*j)] + 1, cache[i]);
    		}
    	}
    	
    	bw.write(String.valueOf(cache[N]));

    	bw.flush();    	
    	bw.close();
    }
}

for문 안에 제곱수인 경우 cache[i] = 1로 만드는 경우와, i부터 1씩 감소하는 j를 이용해서 cache[j] == 1을 만난 경우 cache[i]를 구하는 경우 두 개의 for문을 넣어 코드를 짰더니 시간 초과가 떴다.

알고보니 이중 for문 안쪽에서 (j*j)를 활용해서 cache[0]이 되는 경우 + 1을 하는 방식으로 제곱수를 찾는 방법이 있었다.

그래도 이번에는
꽤 많이 진전이 있었다.