제곱수의 합 (1699)
주어진 자연수 N을 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 문제
11 = 3^2 + 1^2 + 1^2
- 1,2,3 더하기 문제와 매우 유사한 문제.
- 1,2,3 사용 N 방법의 개수
-> 제곱수를 사용해서 N 최소 개수
- D[N]=N을 제곱수의 합으로 나타낼 때의 항의 최소 개수.
- 마지막 수는 뭔지는 모른다. 하지만 i의 제곱이 올 것임.
- 마지막 항은 항 1개이고, i^2이 된다면, 그 앞부분의 합은 N-i^2이 될 것.
- D[i]=i를 제곱수의 합으로 나타냈을 때, 필요한 항의 최소 개수
D[N] = min(D[N-i^2]) + 1 ( 1<=i^2 <=N )
O(n 루트n)이 됨.
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n= sc.nextInt();
int d[]=new int[n+1];
for(int i=1;i<=n;i++) {
d[i]=i;
for(int j=1; j*j <=i;j++) {
//제곱이기 때문에 j*j로 조건식을 설정해준다.
d[i]= Math.min(d[i], d[i-j*j] + 1);
}
}
System.out.println(d[n]);
}
}
원리를 알면 코드 짜는 것은 간단한데... 저렇게 접근하기까지가 어려운 것 같다. 계속 보다보면 익숙해지겠지..
합분해(2225)
0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수
D[K][N] = 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수
-
O + O + O + ... + L = N
-> 여기서 마지막에 오는 수 'L'이 중요함.
-> 전체는 K개이고 L이 빠진 개수는 K-1개임.
-> 전체의 합은 N이고 L이 빠지면 합은 N-L임.
( 0<= L <=N )D[K][N] = 시그마 D[K-1][N-L] (0<=L<=N)
전체 문제는 : KN.
1개 : O(N)
총 시간복잡도는 O(KN^2)
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n= sc.nextInt();
int k= sc.nextInt();
long d[][]=new long[k+1][n+1];
d[0][0] = 1;
for(int i=1;i<=k;i++) {
for(int j=0;j<=n;j++) {
for(int l=0; l<=j; l++) {
d[i][j] += d[i-1][j-l];
d[i][j] %= 1000000000;
}
}
}
System.out.println(d[k][n]);
}
}
=> 3중 for문을 써주었는데 마지막의 l이 마지막으로 오는 수가 되어 중요한 역할을 한다.
퇴사(14501)
이건 예전에 풀었던 문제다. -> brute force를 이용해서 풀었음.
기준 : day -> 상담을 하면 day+T[i] / 상담을 안하면 day+1로 바뀜.
상담을 하게 되면 sum + T[DAY]
-> 다이나믹으로 바꿀 수 있음.
- 작은 문제의 정답에서 큰 문제로 구하고, 작은 문제의 정답을 언제 구해도 같다는 조건이 있으면 BF문제를 DP로 바꿀 수 있음.
- 기존에 풀었던 코드 (brute force)
import java.util.*;
public class Main {
static int n;
static int t[];
static int p[];
static int max =0;
static void go(int day, int sum) {
if(day==n) {
if(max<sum) max=sum;
return;
}
if(day>n) {
return;
}
go(day+1,sum);
go(day+t[day],sum+p[day]);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
t = new int[n];
p = new int[n];
for(int i=0;i<n;i++) {
t[i]=sc.nextInt();
p[i]=sc.nextInt();
}
go(0,0);
System.out.println(max);
}
}- DP를 이용한 코드
import java.util.*;
public class Main {
static int n;
static int t[] = new int[20];
static int p[] = new int[20];
static int d[] = new int[20];
static int go(int day) {
if(day==n+1) {
return 0;
}
if(day>n+1) {
return -10000000;
}
if(d[day] != -1) {
return d[day];
}
int t1 = go(day+1);
int t2= p[day] + go(day+t[day]);
d[day] = Math.max(t1, t2);
return d[day];
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
for(int i=1;i<=n;i++) {
t[i]=sc.nextInt();
p[i]=sc.nextInt();
d[i]=-1;
}
System.out.println(go(1));
}
}=> BF가 훨씬 간단한 것 같다ㅠㅠ... 접근하고 생각하기는 훨씬 쉽지만 BF는 아무래도 경우의 수가 많이 나올 수도 있기때문에 DP로 접근하는 방법을 많이 생각해보아야겠다,,
최백준 선생님의 코딩테스트 기초 강의를 보고 작성한 글입니다.
