#문제

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

 

1956번: 운동

첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2<=V<=400, 0<=E<=V*(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의미이다. (a->b임에 주의) 거리는 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
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
 
#define INF 987654321
vector<pair<int, int> > city[401];
 
int main(){
    // 입력 
    int v, e;
    cin>>v>>e;
    for(int i=0; i<e; i++){
        int start, end, dist;
        cin>>start>>end>>dist;
        city[start].push_back(make_pair(end, dist));
    }
    
    /* 도로 길이의 합이 가장 작은 사이클을 찾고,
       최소 사이클의 도로 길이의 합을 출력
       운동 경로를 찾는 것이 불가능한 경우에는 -1을 출력
    */
 
    // s[i][j]에는 i도시에서 j도시로 가는 최단거리 저장 
    int s[v+1][v+1];
    // s 배열을 모두 INF로 초기화. 
    for(int i=0; i<=v; i++)
        fill_n(s[i], v+1, INF);
    
    // 입력받은 도시 간 연결 도로를 s에 저장한다. 
    for(int i=1; i<=v; i++){
        for(int j=0; j<city[i].size(); j++){
            s[i][city[i][j].first] = city[i][j].second;
        }
    }
    
    // i 도시에서 출발해서 k도시를 거쳐 j도시로 가는 최단거리 계산 
    for(int k=1; k<=v; k++){        // 노드 k를 거쳐간다! 
        for(int i=1; i<=v; i++){
            for(int j=1; j<=v; j++){
                // i에서 출발해서 k를 거쳐 j로 도착한다.
                if( s[i][k]==INF || s[k][j]==INF ) continue;
                if( s[i][k] + s[k][j] < s[i][j] ){
                    s[i][j] = s[i][k] + s[k][j];
                 } 
            }
        }
    }
    
    // s[i][i]에는 i도시에서 출발해서 i도시로 도착하는 최단거리 저장.
    // s[i][i]를 0으로 초기화하지않고 INF로 초기화했으므로
    // 사이클이 형성되는 경우에만 i도시에서 출발해서
    // 돌아서 다시 i도시로 돌아오는 경우의 최단거리가 저장된다 
    int mincycle = 987654321;
    for(int i=1; i<=v; i++){
        mincycle = min( mincycle, s[i][i]);
    }
    
    // 도로 길이 합이 가장 작은 사이클의 도로 길이 합 mincycle 
    if( mincycle !=INF ){
        cout<<mincycle<<'\n';
    }
    else{
        cout<<-1<<'\n';
    }
    return 0; 
}
 cs

##

모든 정점에서 모든 정점까지의 최단거리를 구해야 출발 정점에서 출발정점으로 돌아오는 사이클의 최단거리를 구할 수 있으므로

플로이드 와샬(floyd Warshall)알고리즘을 사용했다.

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 2004번 :: 조합 0의 개수  (0) 2019.12.25
BOJ 1676번 :: 팩토리얼 0의 개수  (0) 2019.12.25
BOJ 1629번 :: 곱셈  (0) 2019.12.24
BOJ 1780번 :: 종이의 개수  (0) 2019.12.24
BOJ 1992번 :: 쿼드트리  (0) 2019.12.24

#문제

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

+ Recent posts

티스토리툴바