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을 하는 방식으로 제곱수를 찾는 방법이 있었다.
그래도 이번에는
꽤 많이 진전이 있었다.
Author And Source
이 문제에 관하여(200925 금 [BOJ] 1699), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kyuhyunhan/200925-금-BOJ-1699저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)