#문제

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

 

1699번: 제곱수의 합

어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는

www.acmicpc.net

 

#작성 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
using namespace std;
 
int n;
int dp[100001];
    //[i] : j를 만드는 방법의 수 
 
int main(){
    // n입력
    cin>>n;
    // dp배열을 1로만 이루어진 제곱수의 합(maximum case)으로 초기화한다. 
    for(int i=0; i<=n; i++){
        dp[i] = i;
    }
    
    for(int i=1; i<=n; i++){
        for(int j=1; j*j<=i; j++){
            dp[i] = min(dp[i], dp[i-j*j]+1);
        }
    }
    
    cout<<dp[n] <<'\n';
    return 0; 
}
 cs

##

n보다 작거나 같은 숫자들에 대해, 제곱수의 합의 최소 개수를 갱신해나가면서 답을 구해주어야 한다.

각 i에 대해, 제곱수의 합으로 i를 구성하는 경우 maximum case는 1+1+...+1의 케이스이다.

-> dp[i] = i로 초기화해준다.

 

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 16500번 :: 문자열 판별  (0) 2020.02.03
BOJ 11052번 :: 카드 구매하기  (0) 2020.02.03
BOJ 9465번 :: 스티커  (0) 2020.02.02
BOJ 2618번 :: 경찰차  (0) 2020.02.01
BOJ 10942번 :: 팰린드롬?  (0) 2020.01.28

#문제

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

 

9465번: 스티커

문제 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다. 모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점

www.acmicpc.net

 

#작성 코드

TOP-DOWN

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
using namespace std;
 
int t, n;
int sticker[2][100000];
int dp[100000][3];
            //[0] : 이전 열에서 아무것도 떼지 않았음
            //[1] : 이전 열에서 상단 스티커를 뗐음
            //[2] : 이전 열에서 하단 스티커를 뗐음 
 
int cal(int col, int status){
    if( col==n )
        return 0;    // n+1열에는 뗄 스티커가 존재하지 않으므로 0을 리턴. 
    if( dp[col][status]!=-1)
        return dp[col][status];
    
    // 1. 아무것도 떼지 않고 다음 열으로 넘어가는 경우 
    int result = cal(col+1, 0);
    // 2. 이전 열의 하단 스티커를 떼지 않았을 경우 -> 하단 스티커도 뗄 수 있다 
    if( status!=2 ){
        result = max(result, sticker[1][col]+cal(col+1, 2));
    }
    // 3. 이전 열의 상단 스티커를 떼지 않았을 경우 -> 상단 스티커도 뗄 수 있다
    if( status!=1 ){
        result = max(result, sticker[0][col]+cal(col+1, 1));
    }
    return dp[col][status] = result; 
}
 
int main(){
    cin>>t;
    while(t--){
        // dp배열을 -1로 초기화한다. 
        for(int i=0; i<100000; i++){
            for(int j=0; j<3; j++){
                dp[i][j] = -1;
            }
        }
        cin>>n;
        for(int i=0; i<2; i++){
            for(int j=0; j<n; j++){
                cin>>sticker[i][j];
            }
        }
        
        // 0열. 0열 이전 열에서 아무것도 떼지 않은 상태에서 시작한다. 
        cout<<cal(0, 0)<<'\n';
    }
    return 0;
}
 cs

BOTTOM UP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
using namespace std;
 
int t, n;
int sticker[2][100000];
int dp[100000][3];
            //[0] : 이전 열에서 아무것도 떼지 않았음
            //[1] : 이전 열에서 상단 스티커를 뗐음
            //[2] : 이전 열에서 하단 스티커를 뗐음 
 
int main(){
    cin>>t;
    while(t--){
        // dp배열을 0으로 초기화한다. 
        for(int i=0; i<100000; i++){
            for(int j=0; j<3; j++){
                dp[i][j] = 0;
            }
        }
        cin>>n;
        for(int i=0; i<2; i++){
            for(int j=0; j<n; j++){
                cin>>sticker[i][j];
            }
        }
        
        for(int i=0; i<n; i++){
            // 다음에 아무것도 안떼는 경우, xx, 1x, 2x의 경우 중 최댓값 선택 
            dp[i+1][0] = max(dp[i+1][0], max(dp[i][0], max(dp[i][1], dp[i][2])));
            // 다음에 상단 스티커를 떼는 경우, x1, 21의 경우 중 최댓값 선택 
            dp[i+1][1] = max(dp[i+1][1], max(dp[i][0], dp[i][2])+sticker[0][i]);
            // 다음에 하단 스티커를 떼는 경우, x2, 12의 경우 중 최댓값 선택
            dp[i+1][2] = max(dp[i+1][2], max(dp[i][0], dp[i][1])+sticker[1][i]); 
        }
        
        // n열까지 스티커를 뗀 경우 중 최댓값을 가지는 경우를 출력한다. 
        cout<<max(dp[n][0], max(dp[n][1], dp[n][2]))<<'\n';
    }
    return 0;
}
 cs

 

##

2n개의 스티커 중, 스티커를 최대한 많이 뗀다면 n개의 스티커를 뗄 수 있다.

이렇게 생각하면 2개의 선택지밖에 없고, 최적해가 포함되지 않는 경우가 발생할 수도 있다.

-> 모든 경우를 살펴보아야한다.

dp[col][status]에 현재까지 뗀 스티커의 가치의 합을 저장한다.

status = col-1열에서 스티커를 뗀 상태

           : 0 = col-1에서 스티커 안뗐음

           : 1 = col-1 상단 스티커 뗐음

           : 2 = col-1 하단 스티커 뗐음

dp[col][status] 배열은 계산 중에 나타날 수 없는 값인 -1로 초기화하고, 이미 계산된 값을 요구한다면 메모이제이션 한 값을 리턴해준다.

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 11052번 :: 카드 구매하기  (0) 2020.02.03
BOJ 1699번 :: 제곱수의 합  (0) 2020.02.02
BOJ 2618번 :: 경찰차  (0) 2020.02.01
BOJ 10942번 :: 팰린드롬?  (0) 2020.01.28
BOJ 2261번 :: 가장 가까운 두 점  (0) 2020.01.27

#문제

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

 

2618번: 경찰차

첫째 줄에는 동서방향 도로의 개수를 나타내는 정수 N(5≤N≤1,000)이 주어진다. 둘째 줄에는 처리해야 하는 사건의 개수를 나타내는 정수 W(1≤W≤1,000)가 주어진다. 셋째 줄부터 (W+2)번째 줄까지 사건이 발생된 위치가 한 줄에 하나씩 주어진다. 경찰차들은 이 사건들을 주어진 순서대로 처리해야 한다. 각 위치는 동서방향 도로 번호를 나타내는 정수와 남북방향 도로 번호를 나타내는 정수로 주어지며 두 정수 사이에는 빈칸이 하나 있다. 두 사건이

www.acmicpc.net

 

#작성 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
 
typedef struct point{
    int x, y;
}point;
int n, w;
 
int dp[1004][1004];        // dp[x][y]는 경찰차1,2가 x, y번째 사건 담당시 이동한 최소거리 저장 
point arr[1004];        // 발생한 사건 좌표 입력. 
 
// 두 좌표간의 맨해튼 거리를 리턴하는 함수. 
int dist(point one, point two){
    return abs(one.x-two.x)+abs(one.y-two.y);
} 
 
int cal(int c1, int c2){
    int curr = max(c1, c2);    // 현재 몇번째 사건까지 처리했는가
    // w+1번째 사건까지 모두 처리한 후에 w+2번째 사건을 처리하려고 하면 종료한다. 
    if( curr == w+2 ) return 0; 
    // c1, c2사건을 처리한 결과가 존재한다면 리턴 
    if( dp[c1][c2] != -1 ) return dp[c1][c2];
    
    // case1. 1번 경찰차가 다음 사건 처리
    int case1 = cal(curr+1, c2)+dist(arr[curr+1], arr[c1]);
    // case2. 2번 경찰차가 다음 사건 처리
    int case2 = cal(c1, curr+1)+dist(arr[curr+1], arr[c2]);     
    return dp[c1][c2] = min(case1, case2);
} 
 
void printSelected(int c1, int c2){
    int curr = max(c1, c2);
    if( curr == w+2 ) return;
    
    int case1 = cal(curr+1, c2)+dist(arr[curr+1], arr[c1]);
    int case2 = cal(c1, curr+1)+dist(arr[curr+1], arr[c2]);
    
    // 1번 경찰차를 선택하는 경우가 되므로. 1출력. 1번 경찰차를 선택한 경우 그 이하의 케이스에 대해 조사. 
    if( case1<case2 ){
        cout<<"1\n";
        printSelected(curr+1, c2);
    }
    else{
        cout<<"2\n";
        printSelected(c1, curr+1);
    } 
}
int main(){
    cin>>n>>w;
    arr[1].x=arr[1].y=1;    // 1번 경찰차(1,1), 2번경찰차(n,n)에서 출발 
    arr[2].x=arr[2].y=n;
 
    // w개의 사건 발생 좌표 입력 (3~w+2번 사건) 
    for(int i=0; i<w; i++){
        cin>>arr[3+i].x>>arr[3+i].y;
    }
    
    // dp배열을 -1로 초기화한다. 
    for(int i=0; i<1004; i++){
        for(int j=0; j<1004; j++){
            dp[i][j]=-1;
        }
    }
    
    cout<<cal(1,2)<<'\n';
    printSelected(1,2);
    
    return 0;
}
 cs

##

 

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 1699번 :: 제곱수의 합  (0) 2020.02.02
BOJ 9465번 :: 스티커  (0) 2020.02.02
BOJ 10942번 :: 팰린드롬?  (0) 2020.01.28
BOJ 2261번 :: 가장 가까운 두 점  (0) 2020.01.27
BOJ 4781번 :: 사탕가게  (0) 2020.01.23

#문제

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

 

10942번: 팰린드롬?

총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다.

www.acmicpc.net

 

#작성 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
 
int n, m;
int serial[2001];
bool result[2001][2001];
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL); 
    
    // n개의 수열 입력 
    cin>>n;
    for(int i=1; i<=n; i++){
        cin>>serial[i];
    }
    
    // 입력된 수열에 대해 팰린드롬 검사
    for(int i=1; i<=n; i++){
        result[i][i] = true;
    }
        
    for(int i=1; i<n; i++){
        if( serial[i] == serial[i+1] ){
            result[i][i+1] = true;
        }
    }
    
    for(int i=2; i<n; i++){    // 길이 2~n-1까지.(j=1일때 1, 2, 3을 탐색...)  
        for(int j=1; j<=n-i; j++){            //(j=n-2일때 n-2, n-1, n 탐색...) 
            // 맨 앞, 맨 뒤 원소 같고
            // 그 사이에 존재하는 수열이 팰린드롬이면 전체는 true 
            if( serial[j]==serial[j+i] && result[j+1][j+i-1] ){
                result[j][j+i] = true;
            }
        }
    }
         
    // m개의 질문 입력 
    cin>>m;
    for(int i=0; i<m; i++){
        int a, b;
        cin>>a>>b;
        // 결과를 출력 
        if( result[a][b] == true ){
            cout<<"1\n";
        }    
        else{
            cout<<"0\n";
        }
    }
    return 0;
}
 cs

##

길이가 1, 2인 경우에는 쉽게 해결할 수 있다.

길이가 3 이상인 경우에는

맨 앞, 맨 뒤가 같으면 안쪽에 존재하는 수열이 팰린드롬이라면 전체가 팰린드롬이 된다!

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 9465번 :: 스티커  (0) 2020.02.02
BOJ 2618번 :: 경찰차  (0) 2020.02.01
BOJ 2261번 :: 가장 가까운 두 점  (0) 2020.01.27
BOJ 4781번 :: 사탕가게  (0) 2020.01.23
BOJ 7579번 :: 앱  (0) 2020.01.23

#문제

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

 

2261번: 가장 가까운 두 점

첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 같은 점이 여러 번 주어질 수도 있다.

www.acmicpc.net

 

#작성 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
struct Point{
    int x, y;
};
 
// 두 점간의 거리^2를 구하는 함수 
long long int distance(Point &a, Point &b){
    long long int dist = (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
    return dist;
}
 
// x좌표를 기준으로 정렬하기 위한 comp함수 
struct comp{
    bool compX;
    comp(bool b):compX(b){}
    bool operator()(Point &a, Point &b){
        return (this->compX?a.x<b.x:a.y<b.y);
    }
};
 
// n개의 점들 중 최단거리를 구하기 위한 함수 
long long int closestPair(vector<Point>::iterator it, int n){
    if( n==2 ){
        return distance(it[0], it[1]);
    }
    else if( n==3 ){
        return min(distance(it[0],it[1]), min(distance(it[1],it[2]), distance(it[0], it[2])));
    }
    
    // n이 3 이상일때 x좌표를 기준으로 기준선을 정한다.
    // 중간에 위치한 두 점의 x좌표의 평균값을 기준선으로 한다. 
    int line =  (it[n/2-1].x + it[n/2].x)/2;
    // line의 좌,우 중에서 최소 거리인 d를 계산한다.
    long long int d = min( closestPair(it, n/2), closestPair(it+n/2, n-n/2) );
    
    vector<Point> mid;
    mid.reserve(n);
    
    for(int i=0; i<n; i++){
        int t = line-it[i].x;
        // x좌표 차이^2이 d보다 작다면 탐색해본다. 
        if( t*t < d ){
            mid.push_back(it[i]);    // 탐색할 대상을 mid에 추가한다 
        }
    }
    
    // line에서 d미만으로 떨어져있는 점들을 y좌표 기준으로 정렬한다. 
    sort(mid.begin(), mid.end(), comp(false));
    // mid에 존재하는 점들 중 d 미만의 dist를 가진다면 d에 업데이트
    int MIDSIZE = mid.size();
    for(int i=0; i<MIDSIZE-1; i++){
        for(int j=i+1; j<MIDSIZE&&(mid[i].y-mid[j].y)*(mid[i].y-mid[j].y) < d; j++){
            d = min( d, distance(mid[i], mid[j]) );
        }
    } 
    return d;
}
 
int main(){
    int n;
    cin>>n;
    
    vector<Point> vp(n);
    for(vector<Point>::iterator it=vp.begin(); it!=vp.end(); it++){
        cin>> it->x >> it->y;
    }
    
    sort(vp.begin(), vp.end(), comp(true));
    cout<<closestPair(vp.begin(), n);
    return 0;
}
 cs

##

분할정복 아이디어는 많이 풀면 잘 떠오르겠지...

많이많이 풀어보자

https://casterian.net/archives/92 참고하였다.

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 2618번 :: 경찰차  (0) 2020.02.01
BOJ 10942번 :: 팰린드롬?  (0) 2020.01.28
BOJ 4781번 :: 사탕가게  (0) 2020.01.23
BOJ 7579번 :: 앱  (0) 2020.01.23
BOJ 1520번 :: 내리막 길  (0) 2020.01.09

#문제

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

 

4781번: 사탕 가게

문제 상근이는 선영이와 걸어가다가 사탕 가게를 지나가게 되었다. 갑자기 상근이는 선영이에게 사탕이 얼마나 건강에 안 좋은지 설명하기 시작했다. 선영이는 매우 짜증이 났고, 상근이에게 누가 더 건강이 안 좋아질 수 있는지 내기를 하자고 했다. 상근이는 내기를 그 즉시 받아들였다. 두 사람은 같은 돈을 가지고 가게에 들어가서 사탕을 산다. 이때, 구매한 사탕의 칼로리가 더 큰 사람이 내기에서 이기게 된다. 상근이는 잠시 화장실에 갔다온다고 핑계를 댄 뒤에,

www.acmicpc.net

 

#작성 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
using namespace std;
 
int n, M;
    // M : m*100    (dp 배열의 인덱스로 가격을 사용하기 위해.) 
int candy[5000][2];
            // [0] : 칼로리
            // [1] : 가격*100 
int dp[10001];
            // 0 ~ 10000을 사용한다. 
 
int main(){
    while(true){ 
        double m;
        cin>>n>>m;
        if( n==0 ) break;        // 0 0.00을 입력받으면 테스트케이스 입력을 끝마친다. 
        M = (int)(m*100+0.5);
        
        // n개의 사탕 정보 저장
        for(int i=0; i<n; i++){
            int c, P; double p;
            cin>>c>>p;
            P = (int)(p*100+0.5);
            candy[i][0] = c;
            candy[i][1] = P;
        }
        fill_n(dp, 10001, 0);
        
        // 돈 m을 가지고 구매할 수 있는 최대 칼로리를 구한다.
        for(int i=0; i<n; i++){
            int cal = candy[i][0];
            for(int ii= candy[i][1]; ii<=M; ii++){
                dp[ii] = max(dp[ii], dp[ii-candy[i][1]]+cal); 
            }
        }
        
        // 최대 칼로리를 찾아 출력한다.
        int result=0;
        for( int i=0; i<10001; i++ ){
            result = max(result, dp[i]);
        }
        cout<<result<<'\n';
    }
    return 0;
} 
 cs

##

7579번 문제와 유사하다는 글을 읽고 복습할 겸 풀어보았다.

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 10942번 :: 팰린드롬?  (0) 2020.01.28
BOJ 2261번 :: 가장 가까운 두 점  (0) 2020.01.27
BOJ 7579번 :: 앱  (0) 2020.01.23
BOJ 1520번 :: 내리막 길  (0) 2020.01.09
BOJ 12015번 :: 가장 긴 증가하는 부분 수열 2  (0) 2020.01.06

+ Recent posts

티스토리툴바