#문제

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

 

1629번: 곱셈

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

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
#include <iostream>
using namespace std;
 
int power(int a, int b, int c){
    // b가 1이 되면 a%c를 리턴한다. 
    if( b==1 ){
        return a%c;
    }
    
    // b가 1이 아닌 짝수이면 a의 b/2제곱을 c로 나눈 나머지 리턴 
    if( b%2==0 ){
        long long int tmp=power(a, b/2, c)%c; 
        tmp *= tmp;
        tmp%=c;
        return tmp;
    }
    // b가 1이 아닌 홀수이면 a* a의 b-1제곱을 c로 나눈 나머지 리턴 
    else{
        long long tmp = power(a, b-1, c)%c;
        tmp *= a;
        tmp%=c;
        return tmp;
    }
}
 
int main(){
    int a, b, c;
    cin>>a>>b>>c;
    cout<<power(a, b, c);
    return 0;
}
 cs

##

power함수의 리턴형을 int로 유지하기 위해 중간 계산과정에 long long int tmp를 추가했다.

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 1676번 :: 팩토리얼 0의 개수  (0) 2019.12.25
BOJ 1956번 :: 운동  (0) 2019.12.25
BOJ 1780번 :: 종이의 개수  (0) 2019.12.24
BOJ 1992번 :: 쿼드트리  (0) 2019.12.24
BOJ 9375번 :: 패션왕 신해빈  (0) 2019.12.23

#문제

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

 

1780번: 종이의 개수

N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다. (1)이 아닌 경우에는 종이를 같은 크기의 9개의 종이로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다. 이와 같이 종이를 잘랐을 때, -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
#include <iostream>
using namespace std;
 
int n;
int paper[2188][2188];
int d[9][2] = {{0,0}, {0,1}, {0,2},
               {1,0}, {1,1}, {1,2},
               {2,0}, {2,1}, {2,2}};
int papernum[3];        // -1, 0, 1으로 채워진 종이의 개수 저장.
                        // 해당 수 +1 인덱스에 값을 저장. 
                        
void cut(int x, int y, int size){
    int first = paper[x][y];
    bool same = true;
    
    if( size==1 ){
        papernum[first+1]++;
        return;
    }
    
    for(int i=x; i<x+size; i++){
        for(int j=y; j<y+size; j++){
            if( paper[i][j]!=first){
                same = false;                
            }
        }
    }
    
    if( same ){
        papernum[first+1]++;
        return;
    }
    else{
        for(int i=0; i<9; i++){
            cut(x+d[i][0]*size/3, y+d[i][1]*size/3, size/3);
        }
    }
}
 
int main(){
    cin>>n;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cin>>paper[i][j];
        }
    }
    
    cut(1, 1, n);
    for(int i=0; i<3; i++){
        cout<<papernum[i]<<'\n';
    }
    return 0;
}
 cs

##

2630 색종이 만들기 문제와 동일하다!

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 1956번 :: 운동  (0) 2019.12.25
BOJ 1629번 :: 곱셈  (0) 2019.12.24
BOJ 1992번 :: 쿼드트리  (0) 2019.12.24
BOJ 9375번 :: 패션왕 신해빈  (0) 2019.12.23
BOJ 2630번 :: 색종이 만들기  (0) 2019.12.22

#문제

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

 

1992번: 쿼드트리

첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1≤N ≤64의 범위를 가진다. 두 번째 줄부터는 길이 N 의 문자열이 N 개 들어온다. 각 문자열은 0 또는 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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <cstdio>
using namespace std;
 
int n;        // max 64
int video[65][65];
 
void compress(int x, int y, int size){
    // 해당범위의 첫 값을 저장 
    int first = video[x][y];
    bool same = true;
    
    // size가 1이라면 무조건 출력한다.(더이상 분할할수없으므로) 
    if( size==1 ){
        cout<<first;
        return;
    }
    
    // 범위 내 값을 첫 값과 비교하며 같지 않다면 same을 false로 바꾼다 
    for(int i=x; i<x+size; i++){
        for(int j=y; j<y+size; j++){
            if( first != video[i][j] ){
                same = false;
            }
        }
    }
    
    // 범위 내 모든 값이 같다면 첫 값을 출력하고 함수 종료 
    if( same ){
        cout<<first;
        return;
    }
    // 범위 내 값이 모두 같지 않다면 4분할하여 비교한다. 
    else{
        cout<<"(";
        compress(x, y, size/2);                    // 2사분면 
        compress(x, y+size/2, size/2);            // 1사분면 
        compress(x+size/2, y, size/2);            // 3사분면 
        compress(x+size/2, y+size/2, size/2);    // 4사분면 
        cout<<")";
    }
    return;
} 
 
int main(){
    // 입력 
    cin>>n;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){ 
            // 한 줄로 입력받는 데이터를 하나하나 배열에 저장한다 
            scanf("%1d", &video[i][j]);
        }
    }
    // 압축 
    compress(1, 1, n);
    return 0;
}
 cs

+) 큐를 이용

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 <cstdio>
#include <queue>
using namespace std;
 
int n;        // max 64
int video[65][65];
queue<char> q;
void compress(int x, int y, int size){
    int first = video[x][y];
    int same = true;
    if( size==1 ){
        if( first==0 ) q.push('0');
        else if( first==1 ) q.push('1');
        return;
    }
    for(int i=x; i<x+size; i++){
        for(int j=y; j<y+size; j++){
            if( first != video[i][j] ){
                same = false;
            }
        }
    }
    
    if( same ){
        if( first ==0 ) q.push('0');
        else if( first==1 ) q.push('1');
        return;
    } 
    else{
        q.push('(');
        compress(x, y, size/2);
        compress(x, y+size/2, size/2);
        compress(x+size/2, y, size/2);
        compress(x+size/2, y+size/2, size/2);
        q.push(')');
    }
 
} 
 
int main(){
    // 입력 
    cin>>n;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            scanf("%1d", &video[i][j]);
        }
    }
    // 압축 
    compress(1, 1, n);
    // 출력
    while(!q.empty()){
        cout<<q.front();
        q.pop();
    }
    cout<<'\n';
    return 0;
}
cs

##

4분할해서 탐색하는 순서를 잘못 입력하는 실수! 방문 순서 잘 체크하자

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 1629번 :: 곱셈  (0) 2019.12.24
BOJ 1780번 :: 종이의 개수  (0) 2019.12.24
BOJ 9375번 :: 패션왕 신해빈  (0) 2019.12.23
BOJ 2630번 :: 색종이 만들기  (0) 2019.12.22
BOJ 2164번 :: 카드2  (0) 2019.12.22

#문제

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

 

9375번: 패션왕 신해빈

문제 해빈이는 패션에 매우 민감해서 한번 입었던 옷들의 조합을 절대 다시 입지 않는다. 예를 들어 오늘 해빈이가 안경, 코트, 상의, 신발을 입었다면, 다음날은 바지를 추가로 입거나 안경대신 렌즈를 착용하거나 해야한다. 해빈이가 가진 의상들이 주어졌을때 과연 해빈이는 알몸이 아닌 상태로 며칠동안 밖에 돌아다닐 수 있을까? 입력 첫째 줄에 테스트 케이스가 주어진다. 테스트 케이스는 최대 100이다. 각 테스트 케이스의 첫째 줄에는 해빈이가 가진 의상의 수

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
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
int tc, n;
vector<pair<string, int> > cloth;    // 옷의 종류, 그 종류 옷 개수
 
int main(){
    cin>>tc;
    while(tc--){
        //초기화
        cloth.clear();
        
        // 입력 
        cin>>n;
        for(int i=0; i<n; i++){
            string name, category;
            cin>>name>>category;
            // 옷장에 옷이 하나도 없으면 무조건 추가! 
            if( cloth.empty()){
                cloth.push_back(make_pair(category, 1));
            }
            else{
                int isin=false;
                // 옷이 하나라도 있으면, 하나하나 비교하면서
                // 새로 입력받은 옷의 종류와 같은 옷이 있는지 체크한다.
                // 있으면 그 종류의 옷 개수를 하나 늘린다. 
                for(int j=0; j<cloth.size(); j++){
                    if( cloth[j].first == category ){
                        cloth[j].second++;
                        isin=true;        // 그 종류 옷이 있음!    
                    }
                }
                // 그 종류 옷이 없으면 옷장에 옷 종류를 추가하고,
                // 그 옷 종류 옷 개수를 하나로 한다. 
                if( !isin ){
                    cloth.push_back(make_pair(category, 1));
                }
            }
        }
        // -> 모든 종류 (옷 수+1)을 곱해서 누적시킨 후 1을 뺀다.
        // -1 : 모든 옷을 입지 않는 경우
        int result=1;
        for(int i=0; i<cloth.size(); i++){
            result*=(cloth[i].second+1);    
        }
        cout<<result-1<<'\n';
    }
    return 0;
}
 cs

##

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 1780번 :: 종이의 개수  (0) 2019.12.24
BOJ 1992번 :: 쿼드트리  (0) 2019.12.24
BOJ 2630번 :: 색종이 만들기  (0) 2019.12.22
BOJ 2164번 :: 카드2  (0) 2019.12.22
BOJ 10845번 :: 큐  (0) 2019.12.22

#문제

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

 

2630번: 색종이 만들기

첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 하얀색으로 칠해진 칸은 0, 파란색으로 칠해진 칸은 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
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
using namespace std;
 
int n;
bool paper[129][129];    // 인덱스 1~128을 사용한다. 
int white=0, blue=0;
int d[4][2] = {{0,0}, {0,1}, {1,0}, {1,1}}; 
 
bool sameColor(int x, int y, int size){
    // (x,y)에서 시작하는 size*size가 모두 같은 색으로 칠해져있는지 체크 
    bool start = paper[x][y];
    bool flag = true;
    // (1,1)에서 시작해서 size가 8인경우, 1,..., 1+8-1까지. 
    for(int i=x; i<x+size; i++){
        for(int j=y; j<y+size; j++){
             if( start != paper[i][j] )
                 flag = false;
        }
    }
    
    // 모든 색이 같다면 
    if( flag ){
        if(start==0)    // 그 색이 흰색이라면 흰 색종이+1 
            white++;
        else            // 그 색이 파란색이라면 파란 색종이+1 
            blue++;
    }
    // 모든 색이 같지 않다면 
    if( !flag ){
        // 4등분해서 같은 색인지 각각 또 비교한다. 
        for(int i=0; i<4; i++){
            sameColor(x+d[i][0]*size/2, y+d[i][1]*size/2, size/2);
        }
    }
    return flag;
}
 
void input(){
    cin>>n;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cin>>paper[i][j];
        }
    }
}
 
int main(){
    input();
    sameColor(1, 1, n);
    cout<<white<<'\n'<<blue<<'\n';
    return 0;
}
 cs

##

sameColor(x, y, size)는 (x,y)에서부터 size*size 크기의 색종이가 모두 같은 색으로 이루어져있는지 판단한다.

모두 같은 색인지는 flag에 저장한다. 같은 색이라면 true, 같은 색이 아니라면 false가 저장된다.

 

만약 flag가 true라면

    모두 같은 색이므로 (x,y)가 무슨 색인지 보고, 그에 해당하는 색종이 조각의 개수를 하나 늘린다.

만약 flag가 false라면

    그 색종이를 가로, 세로로 2등분씩 총 4등분하여 각 조각을 sameColor로 또 비교한다.

    -> sameColor(x, y, size/2)

    -> sameColor(x+size/2, y, size/2)

    -> sameColor(x, y+size/2, size/2)

    -> sameColor(x+size/2, y+size/2, size/2)

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 1992번 :: 쿼드트리  (0) 2019.12.24
BOJ 9375번 :: 패션왕 신해빈  (0) 2019.12.23
BOJ 2164번 :: 카드2  (0) 2019.12.22
BOJ 10845번 :: 큐  (0) 2019.12.22
BOJ 4949번 :: 균형잡힌 세상  (0) 2019.12.22

#문제

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

 

2164번: 카드2

N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다. 예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리

www.acmicpc.net

 

#작성 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <queue>
using namespace std;
 
int n;
 
int main(){
    cin>>n;
    queue<int> q;
    for(int i=1; i<=n; i++)
        q.push(i);
    while(q.size()!=1){
        q.pop();
        int item = q.front();
        q.pop();
        q.push(item);
    }
    cout<<q.front()<<'\n';
    return 0;
}
 cs

##

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 9375번 :: 패션왕 신해빈  (0) 2019.12.23
BOJ 2630번 :: 색종이 만들기  (0) 2019.12.22
BOJ 10845번 :: 큐  (0) 2019.12.22
BOJ 4949번 :: 균형잡힌 세상  (0) 2019.12.22
BOJ 2981번 :: 검문  (0) 2019.12.22

+ Recent posts

티스토리툴바