#문제

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

 

2293번: 동전 1

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,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
#include <iostream>
using namespace std;
 
int n, k;
int coin[101];            // 인덱스 1~100 사용 
int count[10001];        // [k]원을 만드는 경우의 수 저장. 
 
int main(){
    cin>>n>>k;
    for(int i=1; i<=n; i++){
        cin>>coin[i];
    }
    
    count[0]=1;            // 0원을 만드는 경우의 수 1. 
    
    // 1번인덱스의 coin부터 시작.
    // 가치 k를 만드는 경우의 수를 구해서 count[k]에 누적한다. 
    for(int i=1; i<=n; i++){
        for(int j=coin[i]; j<=k; j++){
            count[j] += count[j-coin[i]];
        }
    }
    cout<<count[k]<<'\n';
    return 0;
}
 cs

##

2차원 dp를 사용하면 시간이 너무 오래 걸린다!

재귀를 사용해도 시간이 너무 오래 걸린다!

-> coin[i]에 대해 계산한 경우의 수에 coin[i+1]로 계산한 경우의 수를 더해서 덮어씌운다.

 

ex) 3개의 동전(1, 2, 5)으로 가치의 합 10을 만들어야 하는 경우.

업데이트 되는 부분부터 ( for(int j=coin[i]; j<=k; j++) 부분 ), 업데이트 되는 부분만( += d[j-coin[i]] ) 표시했다.

원 1 2 3 4 5 6 7 8 9 10
1 1 11 111 1111 11111 111111 1111111 11111111 111111111 1111111111
2  

2

2 1

2 11

2 2

2 111

2 2 1

2 1111

2 2 11

2 2 2

2 11111

2 2 111

2 2 2 1

2 111111

2 2 1111

2 2 2 11

2 2 2 2

2 11111111

2 2 11111

2 2 2 111

2 2 2 2 1

2 11111111

2 2 111111

2 2 2 1111

2 2 2 2 11

2 2 2 2 2
5        

5

5 1

5 11

5 2

5 111

5 2 1

5 1111

5 2 11

5 2 2

5 11111

5 2 111

5 2 2 1

5 5
계

1

2

2

3

4

5

6

7

8

10

 

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 1021번 :: 회전하는 큐  (0) 2020.01.03
BOJ 1300번 :: K번째 수  (0) 2020.01.03
BOJ 2110번 :: 공유기 설치  (0) 2019.12.31
BOJ 2805번 :: 나무 자르기  (0) 2019.12.30
BOJ 10866번 :: 덱  (0) 2019.12.28

#문제

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

 

2110번: 공유기 설치

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (1 ≤ xi ≤ 1,000,000,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
#include <iostream>
#include <algorithm>
using namespace std;
 
int n, c;
int house[200001]; 
int mingap = 987654321;
 
void install(){ 
    int low = 1;
    int high = house[n]-house[1];
    int cnt=1;
    long long int gap;
    long long int maxgap=0;
    
    while( low<=high ){
        gap = (low+high)/2;
        int prev=1;        // 직전에 공유기 설치한 집 인덱스 
        // 1번 집에는 무조건 공유기 설치.
        // 앞으로 2번째, ... c번째의 공유기를 설치한다. 
        for(int i=2; i<=c; i++){
            for(int j=prev+1; j<=n; j++){
                if( house[prev]+gap <= house[j] ){
                    cnt++;
                    prev = j;
                    break;
                }
            }
        }
        
        if( cnt >= c ){
            // gap을 조금 더 늘려봐도 되겠다! 
            low = gap+1;
            cnt=1;
            maxgap = gap;        // 이전의 gap은 저장. 
        }
        else{
            high = gap-1;
            cnt=1;
        }
    }
    cout<<maxgap<<'\n';
    return;
}
 
int main(){
    cin>>n>>c;
    for(int i=1; i<=n; i++){
        cin>>house[i];
    }
    // 입력받은 집의 위치 오름차순 정렬. 
    sort(house, house+n+1);
    
    // 1번째집에는 공유기가 반드시 설치되어야
    // 두 공유기 사이의 거리를 최대로 할 수 있다.
    install();
    return 0; 
} 
 cs

##

가장 작은 간격은 1, 가장 큰 간격은 좌표가 가장 큰 집에서 가장 작은 집까지의 거리.

gap = (low + high)/2; 부터 시작해서,

prev에 이전에 공유기를 설치했던 집의 좌표를 저장한다.

첫번째 집부터 최소 gap간격으로 공유기를 설치했을 때 n번째 집까지 도달했을 때 설치해야 할 공유기의 수보다 공유기를 많이 설치했다면(cnt >= c)

이번 gap은 maxgap에 저장하고, cnt를 1로 초기화하고 gap을 조금 늘려서 다시 시도해본다. (cnt=1;)(low = gap+1; )

 

while( low<=high ) 범위를 벗어났다면 탐색할 수 있는 모든 간격을 탐색했으므로 저장된 maxgap을 출력한다.

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 1300번 :: K번째 수  (0) 2020.01.03
BOJ 2293번 :: 동전 1  (0) 2020.01.02
BOJ 2805번 :: 나무 자르기  (0) 2019.12.30
BOJ 10866번 :: 덱  (0) 2019.12.28
BOJ 1654번 :: 랜선 자르기  (0) 2019.12.28

#문제

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

 

2805번: 나무 자르기

문제 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기을 이용해서 나무를 구할것이다. 목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따

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;
// n은 나무의 수. m은 필요한 나무 길이 
int tree[1000000];        // 인덱스 0~1,000,000사용 
int highest=0;            // 가장 높은 높이의 나무 저장 
 
void findmax(){
    int low = 0;
    int high = highest;
    long long int mid;
    long long int result;
    while( low<=high ){
        mid = (low+high)/2;
        long long int sum=0;
        
        // 자르는 길이에서 자르면 잘라지는 부분 sum에 저장 
        for(int i=0; i<n; i++){
            if( tree[i] > mid ){
                sum+=tree[i]-mid;
            }
        }
         
        if( sum>=m ){
            low = mid+1;
            result = mid;
        }
        else if( sum<m ){
            high = mid-1;
        }
    }
    cout<<result<<'\n';
    return;
}
 
int main(){
    cin>>n>>m;
    for(int i=0; i<n; i++){
        cin>>tree[i];
        highest = max(highest, tree[i]);
    }
    findmax();
    return 0;
}
 cs

##

sum>=m 인 경우에 mid를 result에 저장해두어야 이후에 이어진 탐색에서 result를 갱신하지 못해도 while( low<=high )문을 빠져나와도 필요한 길이를 출력할 수 있다.

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 2293번 :: 동전 1  (0) 2020.01.02
BOJ 2110번 :: 공유기 설치  (0) 2019.12.31
BOJ 10866번 :: 덱  (0) 2019.12.28
BOJ 1654번 :: 랜선 자르기  (0) 2019.12.28
BOJ 2049번 :: 피보나치 수 3  (0) 2019.12.28

#문제

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

 

10866번: 덱

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘쨰 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <iostream>
using namespace std;
 
typedef class dequeue{
    private:
    const int f=0;        // 데이터 들어있는 제일 앞 위치 가리킴 
    int b =0;        // 데이터가 들어있는 제일 뒤 다음자리 가리킴 
    int data[10000];
    public:
    void push_front(int x){
        if( b==0 ){
            data[0] = x;
            b = 1;
        }
        else{
            // 한칸씩 데이터 밀고 
            for(int i=b; i>f; i--){
                data[i] = data[i-1];
            }
            data[0] = x;
            b++;
        }
    }
    void push_back(int x){
        if( b==0 ){
            data[0] = x;
            b=1;
        }
        else{
            data[b] = x;
            b++;
        }
    } 
    void pop_front(){
        if( b==0 ){
            cout<<-1<<'\n';
            return;
        }
        else{
            cout<<data[f]<<'\n';
            for(int i=f; i<b; i++){
                data[i] = data[i+1];
            }
            b--;
        }
    }
    void pop_back(){
        if( b==0 ){
            cout<<-1<<'\n';
        }
        else{
            cout<<data[b-1]<<'\n';
            b--;
        }
    }
    void size(){
        cout<<b<<'\n';
    }
    void empty(){
        if( b==0 ) cout<<"1\n";
        else cout<<"0\n";
    }
    void front(){
        if( b==0 ) cout<<"-1\n";
        else cout<<data[f]<<'\n';
    }
    void back(){
        if( b==0 ) cout<<"-1\n";
        else cout<<data[b-1]<<'\n';
    }
}dequeue;
int main(){
    dequeue dq;
    int n;
    cin>>n;
    for(int i=0; i<n; i++){
        string s;
        cin>>s;
        if( s=="push_front" ){
            int x;
            cin>>x;
            dq.push_front(x);
        }else if( s=="push_back" ){
            int x;
            cin>>x;
            dq.push_back(x);
        }else if( s=="pop_front" ){
            dq.pop_front();
        }else if( s=="pop_back"){
            dq.pop_back();
        }else if( s=="size"){
            dq.size();
        }else if( s=="empty"){
            dq.empty();
        }else if( s=="front"){
            dq.front();
        }else if( s=="back"){
            dq.back();
        }
    }
    return 0;
}
 cs

##

AC판정을 받긴 했지만, 데이터를 front에 넣고 뺄때마다 dequeue에 들어있는 data를 인덱스 0에서부터 시작하도록 밀어줬더니 시간이 생각보다 오래 걸렸다.(296ms)

dequeue에 넣을 수 있는 최대 데이터 수를 정해놓고 ex)10,000,000개. front_idx와 back_idx를 사용해서 관리를 하면 front에 push, pop하는 연산 시간을 줄일 수 있겠지!

 

더 정확히 dequeue를 구현하려면 연결리스트를 이용해서,

Node에 int data, Node* next를 저장할 수 있는 Node 구조체를 만들고

Node* front, back으로 관리하면 front에서 push/pop하는 오버헤드가 훨씬 작겠지!

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 2110번 :: 공유기 설치  (0) 2019.12.31
BOJ 2805번 :: 나무 자르기  (0) 2019.12.30
BOJ 1654번 :: 랜선 자르기  (0) 2019.12.28
BOJ 2049번 :: 피보나치 수 3  (0) 2019.12.28
BOJ 10830번 :: 행렬 제곱  (0) 2019.12.27

#문제

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

 

1654번: 랜선 자르기

첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 231-1보다 작거나 같은 자연수이다.

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
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
 
int n, k;
long long int lan[10000];
 
int main(){
    cin>>n>>k;
    long long int high=0;
    for(int i=0; i<n; i++){
        cin>>lan[i];
        high = max(high, lan[i]);
    }
    sort(lan, lan+n);
    int low = 1;
    long long int maxlength=0;
    while( low<=high ){
        long long int mid = (low+high)/2;
        if( mid==0 ) break;
        
        int lannum=0;
        for(int i=0; i<n; i++){
            lannum += lan[i]/mid;
        }
        
        if( lannum>=k ){
            maxlength = max(maxlength, mid);
            low = mid+1;
        }
        else{
            high = mid-1;
        }
    }
    
    cout<<maxlength<<'\n';
    return 0;
}
 cs

##

k=1일 때 가능한 최대 길이는 주어진 랜선 길이 중 가장 긴 것.

k=?일 때 가능한 최대 길이는 1.

-> 1 ~ 주어진 가장 긴 랜선 길이를 이분탐색하며 정답 조건을 만족하는 길이를 찾아나간다.

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 2805번 :: 나무 자르기  (0) 2019.12.30
BOJ 10866번 :: 덱  (0) 2019.12.28
BOJ 2049번 :: 피보나치 수 3  (0) 2019.12.28
BOJ 10830번 :: 행렬 제곱  (0) 2019.12.27
BOJ 10816번 :: 숫자 카드 2  (0) 2019.12.27

#문제

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

 

2749번: 피보나치 수 3

첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,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
#include <iostream>
#include <vector>
using namespace std;
 
long long int n;
int mod = 1000000;
vector<vector<long long int> > one(2, vector<long long int>(2));
 
vector<vector<long long int> > matmul(vector<vector<long long int> > a, vector<vector<long long int> > b){
    int size = a.size();
    vector<vector<long long int> > result(size, vector<long long int>(size));
    
    for(int i=0; i<size; i++){
        for(int j=0; j<size; j++){
            for(int k=0; k<size; k++){
                result[i][j]+=(a[i][k]*b[k][j])%mod;
            }
            result[i][j]%=mod;
        }
    }
    return result;
}
 
vector<vector<long long int> > matpow(vector<vector<long long int> > a, long long int b){
    if( b==0 ){
        return one;
    }
    else if(b==1){
        return a;
    }
    else if(b%2==0){
        vector<vector<long long int> > tmp = matpow(a, b/2);
        return matmul(tmp, tmp);
    }
    else{
        vector<vector<long long int> > tmp = matpow(a, b-1);
        return matmul(a, tmp);
    }
}
 
int main(){
    cin>>n;
    one[0][0]=1; one[1][1]=1;
    
    vector<vector<long long int> > mat(2, vector<long long int>(2));
    mat[0][0]=mat[0][1]=mat[1][0]=1;
    mat[1][1]=0;
    
    vector<vector<long long int> > result(2, vector<long long int>(2));
    result = matpow(mat, n);
    
    cout<<result[0][1]%mod<<'\n';
    return 0;
}
 cs

##

앞서 풀었던 10830 행렬 제곱 문제와 동일한 풀이로 풀 수 있었다.

행렬 제곱을 응용하지 않고, '피사노 주기'라는 것을 이용하면 더 수월하게 풀 수 있다.

 

* 피사노 주기

  주기를 구하는 함수를 만든다면, 항상 F(0) = 0, F(1) = 1임을 이용한다. 0과 1이 반복되는 구간을 찾으면 그 구간이 주기가 된다.

  주기를 찾는다면 그 주기만큼의 피보나치 수를 메모이제이션으로 구하고, n번째 피보나치 수 % k는 (n%주기길이) 번째 피보나치 수를 %k 연산하면 된다.

 

피보나치 수를 구하는 방법에 대해 참고하면 좋을만한 글을 발견했다!

참고 :https://www.acmicpc.net/blog/view/28

 

피보나치 수를 구하는 여러가지 방법

피보나치 수는 다음과 같이 정의되는 수열입니다. $F_0 = 0$ $F_1 = 1$ $F_n = F_{n-1} + F_{n-2}$ 피보나치 수를 조금 써보면, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... 와 같습니다. 피보나치 수를 구하는 함수를 작성해보고 10870번 문제: 피보나치 수 5를 풀어보겠습니다. #include using namespace std; int fibonacci(int n) { if (

www.acmicpc.net

 

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 10866번 :: 덱  (0) 2019.12.28
BOJ 1654번 :: 랜선 자르기  (0) 2019.12.28
BOJ 10830번 :: 행렬 제곱  (0) 2019.12.27
BOJ 10816번 :: 숫자 카드 2  (0) 2019.12.27
BOJ 1966번 :: 프린터 큐  (0) 2019.12.27

+ Recent posts

티스토리툴바