#문제

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

 

11057번: 오르막 수

오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 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
#include <iostream>
using namespace std;
 
int n;
int cnt[1001][10];
// cnt[i][j]는 i자릿수. 일의 자리수가 j인 오르막수의 개수 
// 길이가 n인 오르막 수의 개수를 10007로 나눈 나머지 저장.
 
int main(){
    cin>>n;
    for(int i=0; i<=9; i++){
        // 한자리수 오르막수 
        cnt[1][i]=1;
    }
    
    for(int digit=2; digit<=n; digit++){
        for(int num=0; num<10; num++){
            for(int tmp=0; tmp<=num; tmp++){
                cnt[digit][num] = (cnt[digit][num]%10007+cnt[digit-1][tmp]%10007)%10007;
            }
        }
    }
    
    int cntsum=0;
    for(int i=0; i<10; i++)
        cntsum= (cntsum%10007+cnt[n][i]%10007)%10007;
    cout<<cntsum%10007<<'\n';
    return 0;
} 
 cs

##

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 11049번 :: 행렬 곱셈 순서  (0) 2020.01.06
BOJ 2193번 :: 이친수  (0) 2020.01.05
BOJ 9095번 :: 1, 2, 3 더하기  (0) 2020.01.05
BOJ 11066번 :: 파일 합치기  (0) 2020.01.04
BOJ 6549번 :: 히스토그램에서 가장 큰 직사각형  (0) 2020.01.04

 #문제

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

 

9095번: 1, 2, 3 더하기

문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 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
#include <iostream>
using namespace std;
 
int t, n;
int d[11];
 
int main(){
    cin>>t;
    while(t--){
        fill_n(d, 11, 0);
        d[1]=1;
        d[2]=2;
        d[3]=4;
        cin>>n;
        for(int i=4; i<=n; i++){
            d[i] = d[i-1]+d[i-2]+d[i-3];
        }
        cout<<d[n]<<'\n';
    }
    return 0;
}
 cs

##

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 2193번 :: 이친수  (0) 2020.01.05
BOJ 11057번 :: 오르막 수  (0) 2020.01.05
BOJ 11066번 :: 파일 합치기  (0) 2020.01.04
BOJ 6549번 :: 히스토그램에서 가장 큰 직사각형  (0) 2020.01.04
BOJ 1021번 :: 회전하는 큐  (0) 2020.01.03

#문제

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

 

11066번: 파일 합치기

문제 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 두 개의 파일을

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
#include <iostream>
using namespace std;
 
int t, k;
int ch[501];        // 각 챕터별 파일 사이즈 저장. 인덱스 1~k사용 
int d[501][501]; 
int sum[501];
int INF = 987654321;
int main(){
    cin>>t;
    while(t--){
        cin>>k;
        
        for(int i=1; i<=k; i++){
            cin>>ch[i];
            sum[i] = sum[i-1]+ch[i];
        }
        
        for(int i=1; i<k; i++){            // i : 1 ~ k-1
            for(int a=1; a+i<=k; a++){
                int b = a+i;
                d[a][b] = INF;
                
                for(int mid = a; mid<b; mid++){        // mid : a ~ b-1까지 
                    d[a][b] = min(d[a][b], d[a][mid]+d[mid+1][b]+sum[b]-sum[a-1]);
                                                            // ch[a] + ch[a+1] + ... + ch[b]
                }
            }
        }
        cout<<d[1][k]<<'\n'; 
    }
    return 0;
}
 cs

코드2

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
#include <iostream>
using namespace std;
 
int t, k;
int dp[501][501];
int ch[501];
int sum[501];
int INF = 987654321;
 
int cal(int x, int y){
    if( dp[x][y] != INF ){
        // ch[x] ~ ch[y]까지 합치는 비용 계산된적있다면 return 
        return dp[x][y];
    }
    if( x==y ){
        // ch[x] ~ ch[x] 합치는 비용은 0 
        return dp[x][y] = 0;
    }
    if( x+1==y ){
        // ch[x] ~ ch[x+1] 합치는 비용은 두 파일의 크기 합 
        return dp[x][y] = ch[x]+ch[x+1];
    }
    
    // 어느 부분을 기준으로 이 구간을 두 부분으로 나누는 것이 좋을까
    // ch[x]~ch[mid] + ch[mid+1]~ch[y] 합치는 비용 최솟값 업데이트. 
    for(int mid=x; mid<y; mid++){
        int leftmin = cal(x, mid);
        int rightmin = cal(mid+1, y);
        dp[x][y] = min(dp[x][y], leftmin+rightmin);
    }
    return dp[x][y] += sum[y]-sum[x-1];
}
 
int main(){
    cin>>t;
    while(t--){
        cin>>k;
        for(int i=1; i<=k; i++){
            cin>>ch[i];
            sum[i] = sum[i-1]+ch[i];        // ~ch[i]까지의 누적합 sum[i]에 저장 
        }
        
        // dp[][]를 모두 INF로 초기화. 
        for(int i=1; i<=k; i++){
            for(int j=1; j<=k; j++){
                dp[i][j] = INF;
            }
        }
        
        cout<<cal(1, k)<<'\n';
    }
    return 0;
}
 cs

##

d[i][j] : ch[i] ~ ch[j] 까지 합칠 때 최소 cost 저장.

어렵다... 많이 많이 복습하자

https://js1jj2sk3.tistory.com/3 참고!!

https://kyunstudio.tistory.com/75 참고

https://www.crocus.co.kr/1073 참고

https://boogalle91-cs.tistory.com/32

 

11066 파일 합치기[DP]

S/W 엔지니어를 포기할 까 고민하게 만든 문제였다. 결국 많이 풀어봐야 할 것 같다,, DP문제를 풀 때, 습관적? 고정관념적으로 DP[n] = DP[n-1] + DP[n-2] 처럼 매우 1차원적으로 점진적으로 값이 (오른쪽으로)..

boogalle91-cs.tistory.com

왜 ch[x] + ... ch[y]까지를 더하는지 이해가 안돼서 자료 찾아보는 중..

 

더보기

코드2에 대해서 어떻게 동작하는지 보기 위해 추적한 노트.

dp[1][4]는 두 개씩 묶여서 최소 cost가 되도록 ch[1]~ch[4]까지 합한 cost.

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 11057번 :: 오르막 수  (0) 2020.01.05
BOJ 9095번 :: 1, 2, 3 더하기  (0) 2020.01.05
BOJ 6549번 :: 히스토그램에서 가장 큰 직사각형  (0) 2020.01.04
BOJ 1021번 :: 회전하는 큐  (0) 2020.01.03
BOJ 1300번 :: K번째 수  (0) 2020.01.03

#문제

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

 

6549번: 히스토그램에서 가장 큰 직사각형

문제 히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다. 히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오. 입력 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이

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
103
104
#include <iostream>
#include <cmath>
using namespace std;
 
int n;
int height[100001];        // 인덱스 1~n을 사용한다 
int tree[400001];    // 인덱스 1부터 시작. 
 
void makeTree(int node, int start, int end){
    // 구간의 최소높이가 아니라 단일원소를 가리키므로
    // 해당하는 인덱스를 저장해준다. (리프 노드) 
    if( start==end ){
        tree[node] = start;
    }
    else{
        int mid = (start+end)/2;
        // node의 자식들에 최소높이를 가지는 인덱스를 채운다! 
        makeTree(node*2, start, mid);
        makeTree(node*2+1, mid+1, end);
        
        // 현재 node기준으로 leftChild의 높이 >= rightChild의 높이 일때
        // 현재 node에는 높이 더 작은 rightChild에 저장된 인덱스를 저장. 
        if( height[tree[node*2]] >= height[tree[node*2+1]] ){
            tree[node] = tree[node*2+1];
        }
        else{
        // leftChild 높이 < rightChild높이
        // leftChild에 저장된 인덱스를 현재 node에 저장. 
            tree[node] = tree[node*2];
        }
    }
} 
 
int findminHeight(int start, int end, int node, int left, int right){
    // 구간 내 최소높이를 가지는 인덱스를 리턴하는 함수.
    if( left > end || right < start ){
        // 범위 바깥의 값을 원하면 return -1.(그런 값을 가지는 노드는 없음) 
        return -1;
    }
    if( left <= start && end <= right ){
        // 내가 원하는 구간 내에 현재 탐색범위가 포함되는 경우 
        // --- left ----( start ---- end )---- right --- 
        return tree[node];
    }
    
    int mid = (start+end)/2;
    int m1 = findminHeight(start, mid, node*2, left, right);
    int m2 = findminHeight(mid+1, end, node*2+1, left, right);
 
    if( m1==-1 ){
        return m2; 
    }else if( m2==-1 ){
        return m1;
    }
    else{
        // 높이가 더 작은 인덱스를 리턴 
        if( height[m1] <= height[m2] ){
            return m1;
        }
        else{
            return m2;
        }
    }
} 
 
long long int getMax(int start, int end){
    // start ~ end 구간 내의 최대넓이를 찾아서 리턴.
    
    // start-end구간 내의 최소높이를 가지는 인덱스 찾는다. 
    int hIndex = findminHeight(1, n, 1, start, end);
    // 최소높이에 대한 구간 내의 최대넓이 area에 저장. 
    long long int area = static_cast<long long int>(end-start+1)*static_cast<long long int>(height[hIndex]);
    
    // 최소높이를 가지는 인덱스 좌측에 다른 인덱스 존재하면
    // 좌측에 대해서 재귀적으로 최대넓이를 구해서 area에 최대넓이를 업데이트. 
    if( start <= hIndex-1 ){
        long long int tmpArea = getMax(start, hIndex-1);
        area = max(area, tmpArea);
    }
    
    // 최소높이를 가지는 인덱스 우측에 다른 인덱스 존재하면
    // 우측에 대해 재귀적으로 최대넓이를 구해서 area에 최대넓이를 업데이트. 
    if( hIndex+1 <=end ){
        long long int tmpArea = getMax(hIndex+1, end);
        area = max(area, tmpArea);
    }
    
    return area;
} 
 
int main(){
    // 0이 하나 입력될때까지 반복 
    while(true){
        cin>>n;
        if( n==0 ) return 0;
        fill_n(height, n+1, 0);        // 0으로 height를 초기화 
        for(int i=1; i<=n; i++){
            cin>>height[i];
        }    
        
        makeTree(1, 1, n);
        cout<<getMax(1, n)<<'\n'; 
    }
}
 cs

##

데이터의 크기가 크기도 하고, 어떻게 접근해야 효율적으로 풀 수 있을지 떠올리기 너무너무너무너무 어려웠다.

처음엔 2차원 dp로 접근해봤는데 d[100001][100001] 배열의 사이즈가 너무 크고, 각 케이스별 최소높이를 구하는 과정까지 더하면 시간 복잡도가 O(n^3)정도로 거대해져서 풀 수 없었다.

 

어떻게 풀면 좋을지 검색으로 배웠다. 모르는건 빨리 배우고 익숙해져야지

https://www.crocus.co.kr/707

 

[6549번] 히스토그램에서 가장 큰 직사각형

문제 출처 : https://www.acmicpc.net/problem/6549 알고리즘 분석 : 문제 해결에 필요한 사항 1. 세그먼트 트리(Segment Tree) :: http://www.crocus.co.kr/648 세그먼트 트리를 이용하여 O(nlgn)에 해결 할 수..

www.crocus.co.kr

https://m.blog.naver.com/PostView.nhn?blogId=occidere&logNo=221057769152&proxyReferer=https%3A%2F%2Fwww.google.com%2F

 

[백준] 6549 - 히스토그램에서 가장 큰 직사각형

문제 링크: https://www.acmicpc.net/problem/6549 스택으로 분류되어 있는데 감이 안와서 세그먼트 트리 +...

blog.naver.com

세그먼트 트리에 대해 https://m.blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221282210534&proxyReferer=https%3A%2F%2Fblog.naver.com%2Fndb796%2F221282210534 에서 공부했다. 백준의 단계별로 풀어보기에서 이전에 등장하지 않았던 풀이 방식이라 이 문제에 좀 더 익숙해지고, 비슷한 문제를 더 풀어봐야겠다.

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 9095번 :: 1, 2, 3 더하기  (0) 2020.01.05
BOJ 11066번 :: 파일 합치기  (0) 2020.01.04
BOJ 1021번 :: 회전하는 큐  (0) 2020.01.03
BOJ 1300번 :: K번째 수  (0) 2020.01.03
BOJ 2293번 :: 동전 1  (0) 2020.01.02

#문제

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

 

1021번: 회전하는 큐

첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다. 위치는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.

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
#include <iostream>
#include <deque>
using namespace std;
 
int n, m;
deque<int> dq;
int count=0;
 
void pop(){
    dq.pop_front();
}
void right(){
    // 우측 순환 회전 <<-
    dq.push_back(dq.front());
    dq.pop_front();
    count++;
}
void left(){
    // 좌측 순환 회전 ->>
    dq.push_front(dq.back());
    dq.pop_back();
    count++;
}
 
int main(){
    cin>>n>>m;
    
    for(int i=1; i<=n; i++)
        dq.push_back(i);
    
    for(int i=0; i<m; i++){
        int num;
        cin>>num;
        
        // 바로 front에서 num을 뽑아낼 수 있다면 뽑아낸다. 
        if( dq.front()==num ){
            pop();
            continue;
        }
        
        int idx=0;
        // 지금 입력받은 num이 dq의 몇 번째에 위치하는지 찾는다.
        for(int i=0; i<dq.size(); i++){
            if( dq[i]==num){
                idx=i;
                break;
            }
        }
        
        // 좌측으로 회전시키는것, 우측으로 회전시키는 것 중
        // 어느 쪽이 더 빠른지 계산
        if( idx <= dq.size()-idx ){
            // 앞에서부터 세는 것이 빠른 경우
            // 우측 순환 회전 시키며 front 같을 때까지 찾는다. 
            while(true){
                right(); 
                if( dq.front()==num ){
                    pop();
                    break;
                }
            }
        }
        else{
            // 뒤에서부터 세는 것이 빠른 경우
            // 좌측 순환 회전 시키며 front 같을 때까지 찾는다. 
            while(true){
                left();
                if( dq.front()==num){
                    pop();
                    break;
                }
            }
        }
    }
    cout<<count<<'\n';
    return 0;
    
}
 cs

##

큐는 임의의 위치에 존재하는 값을 참조할 수 없지만, 덱은 벡터처럼 임의의 위치에 존재하는 값을 참조할 수 있다.

-> 덱을 사용한다!

 

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 11066번 :: 파일 합치기  (0) 2020.01.04
BOJ 6549번 :: 히스토그램에서 가장 큰 직사각형  (0) 2020.01.04
BOJ 1300번 :: K번째 수  (0) 2020.01.03
BOJ 2293번 :: 동전 1  (0) 2020.01.02
BOJ 2110번 :: 공유기 설치  (0) 2019.12.31

#문제

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

 

1300번: K번째 수

첫째 줄에 배열의 크기 N이 주어진다. N은 105보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다. k는 min(109, n2)보다 작거나 같은 자연수이다.

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
#include <iostream>
using namespace std;
 
long long int n, k;
 
int main(){
    cin>>n>>k;
    
    long long int small = 1;
    long long int big = n*n;
    long long int x;
    long long int answer;
    
    while( small<=big ){
        x = (small+big)/2;
        long long int numunderX=0;        // x이하 수의 개수 
        
        for(int i=1; i<=n; i++){
            numunderX+=min(x/i, n);
        }
        
        if( numunderX>=k ){
        // x이하 수의 개수가 k개보다 많으므로 x를 줄여야한다.
            big = x-1;
            answer = x;        // 현재 x를 저장,
                            // 만약 다음 numunderX가 조건을 만족하지 못하면
                            // answer는 갱신되지 않는다. 
        }
        else{
        // numunderX<k 일 때
        // x를 크게 해야 한다. 
            small = x+1;
        }
    }
    cout<<answer<<'\n';
    return 0;
}
 cs

##

'x이하 수의 개수가 k개 있다'를 만족하는 x를 찾는 것이 핵심!

가능한 x의 범위 1~n*n 내에서 이분 탐색을 통해 조건을 만족하는 x를 찾는다.

 

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 6549번 :: 히스토그램에서 가장 큰 직사각형  (0) 2020.01.04
BOJ 1021번 :: 회전하는 큐  (0) 2020.01.03
BOJ 2293번 :: 동전 1  (0) 2020.01.02
BOJ 2110번 :: 공유기 설치  (0) 2019.12.31
BOJ 2805번 :: 나무 자르기  (0) 2019.12.30

+ Recent posts

티스토리툴바