#문제

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

 

10845번: 큐

첫째 줄에 주어지는 명령의 수 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
#include <iostream>
using namespace std;
 
typedef class queue{
    private:
    int qsize=-1;
    int data[10001];
    public:
    void push(int x){
        qsize++;
        data[qsize] = x;
    }
    void pop(){
        if( qsize==-1 ){
            cout<<-1<<'\n';
            return;
        }
        cout<<data[0]<<'\n';
        for(int i=1; i<=qsize; i++){
            data[i-1] = data[i];
        }
        qsize--;
    }
    void size(){
        cout<<qsize+1<<'\n';
    }
    void empty(){
        if( qsize==-1 ) cout<<1<<'\n';
        else cout<<0<<'\n';
    }
    void front(){
        if( qsize==-1){
            cout<<-1<<'\n';
            return;
        }
        cout<<data[0]<<'\n';
    }
    void back(){
        if( qsize==-1){
            cout<<-1<<'\n';
            return;
        }
        cout<<data[qsize]<<'\n';
    }
}queue; 
 
int main(){
    int n;
    cin>>n;
    queue q;
    // n개의 명령어 입력 
    for(int i=0; i<n; i++){
        string com;
        int num;
        cin>>com;
        if(com=="push"){
            cin>>num;
            q.push(num);
        }
        else if(com=="pop"){
            q.pop();
        }
        else if(com=="size"){
            q.size();
        }
        else if(com=="empty"){
            q.empty();
        }
        else if(com=="front"){
            q.front();
        }
        else if(com=="back"){
            q.back();
        }
    }
    return 0;
}
 cs

##

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 2630번 :: 색종이 만들기  (0) 2019.12.22
BOJ 2164번 :: 카드2  (0) 2019.12.22
BOJ 4949번 :: 균형잡힌 세상  (0) 2019.12.22
BOJ 2981번 :: 검문  (0) 2019.12.22
BOJ 10217번 :: KCM Travel  (0) 2019.12.21

#문제

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

 

4949번: 균형잡힌 세상

문제 세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다. 정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다. 문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 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
#include <iostream>
#include <string>
#include <stack>
using namespace std;
 
int main(){
    while(true){
        string s;
        stack<char> st;
        getline(cin, s);
        
        // '.'만 입력받으면 종료한다. 
        if( s.length()==1 && s[0]=='.' )
            break;
            
        bool flag = true;
        // 입력받은 문자열의 길이만큼 반복. 모든 인덱스 방문                
        for(int i=0; i<s.length(); i++){
            if( s[i]=='('){    // 여는 괄호 만나면 push 
                st.push('(');
            }
            else if( s[i]=='[' ){
                st.push('[');
            }
            else if( s[i]==')'){        // 닫는괄호 )만났을때 
                if( !st.empty()&&st.top()=='(' ){    // 스택 top이 (이면 스택 pop 
                    st.pop();
                }
                else{
                    flag = false;
                    break;
                }
            }
            else if(s[i]==']'){            // 닫는괄호 ]만났을때 
                if( !st.empty() && st.top()=='['){    // 스택 top이 [이면 스택 pop 
                    st.pop();
                }
                else{
                    flag = false;
                    break;
                }
            }
        }
        
        if( flag && st.empty() )
            cout<<"yes\n";
        else
            cout<<"no\n";
    }
    return 0;
}
 cs

##

공백을 포함한 문자열을 입력받아야 하므로 getline(cin, str)을 사용했다.

만약 입력받은 문자열의 길이가 1이고, '.'이 첫 문자이면, 무한루프를 종료한다.

문자열의 인덱스 i:  0 ~ 문자열길이를 탐색한다.

s[i] 가 ( 또는 [이면 스택에 해당 문자를 push하고,

s[i] 가 ) 또는 ] 일 때 스택이 비어있지 않고, 스택의 최상단이 해당 문자의 괄호쌍이면 스택에서 pop한다. 만약 그렇지 않다면 no를 출력하도록 break한다.

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 2164번 :: 카드2  (0) 2019.12.22
BOJ 10845번 :: 큐  (0) 2019.12.22
BOJ 2981번 :: 검문  (0) 2019.12.22
BOJ 10217번 :: KCM Travel  (0) 2019.12.21
BOJ 11653번 :: 소인수분해  (0) 2019.12.21

#문제

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

 

2981번: 검문

문제 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간을 때우기 위해서 수학 게임을 하기로 했다. 먼저 근처에 보이는 숫자 N개를 종이에 적는다. 그 다음, 종이에 적은 수를 M으로 나누었을 때, 나머지가 모두 같게 되는 M을 모두 찾으려고 한다. M은 1보다 커야 한다. N개의 수가 주어졌을 때, 가능한 M을 모두 찾는

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
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
 
int n;
int num[100];
vector<int> prime;
 
int gcd(int a, int b){
    return a%b?gcd(b, a%b):b;
}
 
int main(){
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>num[i];
    }
    sort(num, num+n);
    int Gcd = num[1]-num[0];    
    for(int i=2; i<n; i++){
        Gcd = gcd(Gcd, num[i]-num[i-1]);
    }
 
    // 최대공약수의 약수 찾기!!
    // 약수를 찾으면 하나씩 prime 벡터에 넣는다. 
    for(int i=1; i*i<=Gcd; i++){
        if( Gcd%i==0 ){
            prime.push_back(i);
            if( i==1 ) prime.pop_back();
            if(Gcd/i==i) continue;
            prime.push_back(Gcd/i);
        }
    }
    sort(prime.begin(), prime.end());
    for(int i=0; i<prime.size(); i++){
        cout<<prime[i]<<' ';
    }
    return 0;
}
 cs

##

입력받은 숫자를 a0, a1, ... an-1이라고 하면 m이 하나 이상 존재하는 입력이 들어오므로

a0 = m*b0 + d

a1 = m*b1 + d

...

an-1 = m*bn-1 + d

의 꼴이 된다.

따라서 an-1 - an-2 = m(bn-1 - bn-2), ... , a1-a0 = m(b1-b0) 이 되므로

i=1 ~ n-1에서 ai-ai-1들의 최대공약수를 구하면 모든 ai에 대해 m*bi를 나눠떨어지도록 하는 수가 된다.

그 최대 공약수를 k라고 하면, k의 약수들도 m*bi를 나눠떨어지게 할 수 있다.

=> k를 구하고, k의 약수들을 오름차순으로 출력하면 되는 문제.

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 10845번 :: 큐  (0) 2019.12.22
BOJ 4949번 :: 균형잡힌 세상  (0) 2019.12.22
BOJ 10217번 :: KCM Travel  (0) 2019.12.21
BOJ 11653번 :: 소인수분해  (0) 2019.12.21
BOJ 11404번 :: 플로이드  (0) 2019.12.20

#문제

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

 

10217번: KCM Travel

각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세에 힘입어 구글 역시 대기업답게 비용 감축에 열을 내고 있었던 것이다. 초대장 내용에 의하면 구글은 찬민에게 최대 M원까지의 비용만을 여행비로써 부담해주겠다고 한다. 인천에서 LA행 직항 한 번 끊어주는게 그렇게 힘드냐고 따지고도 싶었지만,

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
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
 
int tc, n, m, k;
vector<pair<int, pair<int, int> > > air[101];        // 인덱스 1~100 사용 
// air[출발공항]에 도착공항, 비용, 소요시간 저장. 
priority_queue<pair<int,pair<int, int> > > pq;
int path[101][10001];
// 1번에서 i로 가는 최소 티켓가격1~10000에 따른 이동시간[i][1~10000] 저장. 
// 예산 내의 각 cost에 대해서 이동시간을 계산하고, n번째 공항의 각 cost에 따른 이동시간 중 최단시간을 고르자 
int INF = 987654321;
 
int main(){
    cin>>tc;
    while(tc--){
        // air 벡터와 path배열 초기화
        for(int i=0; i<101; i++){
            air[i].clear();
            fill_n(path[i], 10001, INF);
        }
        path[1][0] = 0;        // 인천은 언제나 인덱스 1, 모든 cost 에 대해 0 
        
        // 입력
        cin>>n>>m>>k;
        for(int i=0; i<k; i++){
            int start, dest, cost, time;
            cin>>start>>dest>>cost>>time;
            air[start].push_back(make_pair(dest, make_pair(cost, time)));
        }
        // 1으로 가는 비용 음수화한 것, 1으로 가는 최단시간, 출발공항 번호 1 
        pq.push(make_pair(0,make_pair(0, 1)));
        
        while(!pq.empty()){
            int nowcost = -pq.top().first;
            int nowtime = pq.top().second.first;
            int now = pq.top().second.second;
            pq.pop(); 
            
            if( path[now][nowcost] < nowtime ) continue;
            for(int i=0; i<air[now].size(); i++){
                int next = air[now][i].first;
                int nextcost = air[now][i].second.first+nowcost;
                int nexttime = air[now][i].second.second+nowtime;
                 
                // 1~now 비용 + now~next 비용 <= 예산(m) 일 때
                // 소요시간이 단축된다면 업데이트 한다.
                if( nextcost <= m ){
                    if( nexttime < path[next][nextcost] ){
                        path[next][nextcost] = nexttime;
                        pq.push(make_pair(-nextcost, make_pair(nexttime, next)));
                    }
                }
            }
        } 
        
        int mintime=INF;
        for(int i=0; i<=m; i++){
            mintime = min(mintime,path[n][i]);
        }
        if( mintime!=INF ){
            cout<<mintime<<'\n';
        }
        else{
            cout<<"Poor KCM\n";
        }
    }
    return 0; 
}
 cs

##

인천(1번 노드)에서 출발해서 무조건 LA(n번 노드)로 가는 최단 비행 시간을 구해야 한다.

단일 출발지~ 다른 모든 노드로까지의 최단 경로를 구하는 다익스트라 알고리즘을 사용했다.

 

처음에는 예산 내에서 새로 생기는 cost가 예산 내라면 항상 업데이트하면서 그에 따른 비행시간이 단축된다면 업데이트 했는데,

이렇게 풀면 중간 노드까지의 최단비행시간이 아니더라도, 최종 목적지까지 가는 최단비행경로에 포함되는 간선이 있다면 업데이트 할 수 없게된다.

-> 각 노드까지 가는 cost가 어떤지에 따른 최단 비행시간을 업데이트해서 해결했다.

path[101][10001] : path[i][m]에는 i노드까지 가는 cost가 m일 때 최단비행시간을 저장한다.

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 4949번 :: 균형잡힌 세상  (0) 2019.12.22
BOJ 2981번 :: 검문  (0) 2019.12.22
BOJ 11653번 :: 소인수분해  (0) 2019.12.21
BOJ 11404번 :: 플로이드  (0) 2019.12.20
BOJ 1541번 :: 잃어버린 괄호  (0) 2019.12.20

#문제

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

 

11653번: 소인수분해

첫째 줄에 정수 N (1 ≤ N ≤ 10,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
#include <iostream>
#include <algorithm>
using namespace std;
 
int n;
int prime[10000000];
int numprime=0;
int INF = 10000000;
int main(){
    cin>>n;
    int tmp = n;
    
    for(int i=2; i<=n; i++){
        prime[i] = i;
    }
    for(int i=2, j; i*i<=n; i++){
        if( prime[i]==i ){
            numprime++;
            for(int j=i+i; j<=n; j=j+i){
                prime[j]=INF;
            }
        }
    }
    sort(prime, prime+numprime);
 
    int i=2;
    while(tmp!=1){
        while(tmp%prime[i]==0){
            tmp/=prime[i];
            cout<<prime[i]<<'\n';
        }
        i++;
    }
    return 0;
}
 cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
using namespace std;
 
int n;
int main(){
    cin>>n;
    int tmp = n;
    
    for(int i=2; i<=n; i++){
        while(tmp%i==0){
            tmp/=i;
            cout<<i<<'\n';
        }
    }
    return 0;
}
 cs

##

첫 코드는 에라토스테네스의 체를 이용한 코드이다. 200ms정도의 수행시간을 보였다.

두 번째 코드는 2부터 n까지 단순히 나누어떨어지지않을때까지 나눠서 n을 1로 만드는 방식이다. 약 32ms의 수행시간을 보였다.

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 2981번 :: 검문  (0) 2019.12.22
BOJ 10217번 :: KCM Travel  (0) 2019.12.21
BOJ 11404번 :: 플로이드  (0) 2019.12.20
BOJ 1541번 :: 잃어버린 괄호  (0) 2019.12.20
BOJ 1865번 :: 웜홀  (0) 2019.12.19

#문제

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

 

11404번: 플로이드

첫째 줄에 도시의 개수 n(1 ≤ n ≤ 100)이 주어지고 둘째 줄에는 버스의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 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
#include <iostream>
using namespace std;
 
int n, m;
int path[101][101];
int INF = 100000000;
 
void init(){
    // 모든 경로를 INF로 초기화한다. 
    for(int i=0; i<=n; i++){
        for(int j=0; j<=n; j++){
            path[i][j] = INF;
            // 자기 자신으로 가는 거리는 0
            if( i==j ) path[i][j] = 0;
        }
    }
}
 
void floyd(){
    // 플로이드 와샬 알고리즘 시작 
    for(int k=1; k<=n; k++){
        for(int i=1; i<=n; i++){        // i에서 출발 
            for(int j=1; j<=n; j++){    // j로 도착하는데, k를 경유한다. 
                // 경유거리 중 무한대가 없을때만 경유함 
                if( path[i][k]!=INF && path[k][j]!=INF ) 
                    path[i][j] = min(path[i][j], path[i][k] + path[k][j]);
            }
        }
    }
}
 
int main(){
    cin>>n>>m;
    init();
    // 버스 출발지, 도착지, 걸리는 시간 입력. 
    for(int i=0; i<m; i++){
        int s, e, d;
        cin>>s>>e>>d;
        // path 배열 업데이트 
        // 연결된 간선 중 가장 짧은 것으로 업데이트하자 
        path[s][e] = min(path[s][e], d);
    }
    floyd();
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(path[i][j]==INF || path[i][j]==0)
                cout<<0<<' ';
            else
                cout<<path[i][j]<<' ';
        }
        cout<<'\n';
    }
    return 0;
}
 cs

##

플로이드 와샬 알고리즘에는 전혀 문제가 없는데, 왜 자꾸 틀린 결과값이 출력되는지 답답했는데

문제를 제대로 읽지 않은 것이었다. 문제에 오해의 소지가 있다고 해야하나..?? 나만 그렇게 이해한걸까

각 간선은 버스인데, 나는 두 도시를 잇는 버스 노선이 양방향이라고 생각했는데, 혹시나 해서 단방향으로 고쳤더니 맞았다.

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 10217번 :: KCM Travel  (0) 2019.12.21
BOJ 11653번 :: 소인수분해  (0) 2019.12.21
BOJ 1541번 :: 잃어버린 괄호  (0) 2019.12.20
BOJ 1865번 :: 웜홀  (0) 2019.12.19
BOJ 11399번 :: ATM  (0) 2019.12.18

+ Recent posts

티스토리툴바