#문제

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

 

1541번: 잃어버린 괄호

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 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>
#include <vector>
#include <string>
using namespace std;
string s;
 
int main(){
    cin>>s;
    vector<int> num;
    vector<char> op;
    int tmp;
    /* 숫자와 연산자를 파싱한다. */
    for(int i=0; i<s.length(); i++){
        tmp=0;
        // 숫자인 경우 
        if( s[i]!='+' && s[i]!='-' ){
            if(i-1>=0 && s[i-1]!='+' && s[i-1]!='-'){    // 이전 위치도 숫자였다면 연결해야하니까. 
                tmp = num.back();    // 가장 최근 숫자 벡터에서 꺼내고 
                num.pop_back();        // 가장 최근 숫자 벡터에서 삭제 
                tmp = tmp*10;         // 한자릿수 늘린다. 
            }
            tmp += static_cast<int>(s[i]-'0');
            num.push_back(tmp);        // 벡터에 삽입. 
        }
        // 연산자인 경우 
        else{
            op.push_back(s[i]);
        }
    }
 
    /* 실제 계산을 수행하는 부분 */
    // 최대한 많이 빼고, 적게 더한다.
    // -를 만나기 이전에는 모든 숫자를 더해준다. 
    // == -를 만나면 이후 숫자들은 모두 빼준다. 
    // '-' 이후에 나타나는 '+'들은 -(a+b+c)-(d+e) 와 같이 모두 -로 바꿀 수 있으므로 
    
    tmp = num[0];    // tmp를 계산 결과 저장용으로 재활용하자. 
    for(int i=0, j=0; i<num.size()&&j<op.size(); ){
        if( op[j]=='-' ){
            while(j!=op.size()){
                tmp-=num[++i];
                j++;    
            }
            break;
        }
        else if( op[j]=='+'){
            tmp+=num[++i];
            j++;
        }
    }
    cout<<tmp<<'\n';
    return 0;
}
 cs

##

최대한 많이 빼고, 적게 더해야 식의 결과를 최소로 만들 수 있다.

-> 처음 '+' 연산자를 만나면 덧셈 연산을 진행하고, '-' 연산자를 만난 이후에는 다음 연산자에 관계없이 차례로 뺄셈을 진행하도록 했다.

    왜냐하면, '-' 연산자 이후에 만나는 '+' 연산자들은 그 다음에 다시 '-' 연산자 만날 때까지 괄호로 묶어서 더 큰 수를 뺄 수 있도록 처리해주면 되기 때문이다.

ex) 50 - 1 + 2 + 3 - 4 + 5

=> 50 - (1 + 2+ 3) - (4 + 5)

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 11653번 :: 소인수분해  (0) 2019.12.21
BOJ 11404번 :: 플로이드  (0) 2019.12.20
BOJ 1865번 :: 웜홀  (0) 2019.12.19
BOJ 11399번 :: ATM  (0) 2019.12.18
BOJ 1931번 :: 회의실 배정  (0) 2019.12.18

#문제

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

#작성 코드

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
#include <iostream>
#include <vector>
using namespace std;
 
int tc, n, m, w;
int INF = 987654321;
int s[501];        // s[i]로 가는 최단시간 저장 
vector<pair<int,int> > p[501];
bool flag;        // 음의 사이클 발생 여부 
 
int main(){
    cin>>tc;
    while(tc--){
        // 음의 사이클 발생여부, 도로, 웜홀 연결들, s배열을 초기화해준다. 
        flag = false;
        for(int i=0; i<501; i++)
            p[i].clear();
        fill_n(s, n, INF);
        s[1] = 0;
        
        // 지점, 도로, 웜홀 개수 입력 
        cin>>n>>m>>w;
        // m개 도로 입력. 양방향. 
        for(int i=0; i<m; i++){
            int s, e, t;
            cin>>s>>e>>t;
            p[s].push_back(make_pair(e, t));
            p[e].push_back(make_pair(s, t));
        }
        // w개 웜홀 입력. 단방향. 음의 가중치.
        for(int i=0; i<w; i++){
            int s, e, t;
            cin>>s>>e>>t;
            p[s].push_back(make_pair(e, -t));
        }
        
        // 벨만 포드 알고리즘은 O(V*E)이다. 
        // 지점 개수 (V) 
        for(int i=1; i<=n; i++){
        // * 도로, 웜홀 개수(E) 
            for(int j=1; j<=n; j++){
                for(int k=0; k<p[j].size(); k++){
                    int next = p[j][k].first;
                    int cost = p[j][k].second;
                    if( s[j]!=INF && s[next]>cost+s[j]){
                        s[next] = cost + s[j];
                        if( i==n ){
                            // 음의 사이클 발생시 flag를 true로 한다. 
                            flag = true;
                        }
                    }
                }
            }
        }
        if(flag)
            cout<<"YES\n";
        else
            cout<<"NO\n";
    }
    return 0;
}
 cs

 

travel 함수로 벨만포드 알고리즘을 분리한 코드.

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
#include <iostream>
#include <vector>
using namespace std;
 
vector<pair<int,int> > p[501];
int testcase, point, road, worm;
int time[501];
int INF = 2000000000;
 
bool travel(){
    for(int i=1; i<=point; i++){
        for(int j=1; j<=point; j++){
            for(int k=0; k<p[j].size(); k++){
                int next = p[j][k].first;
                int takes = p[j][k].second+time[j];
                
                if( time[j]!=INF && takes<time[next] ){
                    if( i==point ){
                        return true;
                    }
                    time[next] = takes;
                }
            }
        }
    }
    return false;
}
 
int main(){
    cin>>testcase;
    for(int tc=0; tc<testcase; tc++){
        // 1번 지점에서 각 지점으로 가는데 걸리는 시간 무한대로 초기화 
        for(int init=0; init<501; init++){
            time[init] = INF;
        }
        // 시작 지점에서 시작지점으로 가는 시간은 0이다. 
        time[1] = 0;
        for(int i=0; i<501; i++){
            p[i].clear();
        }
        
        // 입력
        cin>>point>>road>>worm;
        for(int r=0; r<road; r++){
            int s, e, t;
            cin>>s>>e>>t;
            // 도로는 양방향(=무방향)이다. 
            p[s].push_back(make_pair(e, t));
            p[e].push_back(make_pair(s, t));
        }
        for(int w=0; w<worm; w++){
            int s, e, d;
            cin>>s>>e>>d;
            // 웜홀은 단방향이다.
            // 웜홀에서는 시간이 거꾸로 흐르므로 -d로 저장해준다. 
            p[s].push_back(make_pair(e, -d));
        }
        // 음의 사이클이 존재하면 yes
        // (음의 사이클 중 하나에서 출발하면 출발지로 돌아오면 과거가 된다.)
        if( travel() ) cout<<"YES\n";
        else cout<<"NO\n";
    }
    return 0;
}
 cs

##

벨만포드 알고리즘 로직은 틀리지 않았는데, 자꾸 틀렸다는 판정을 받아서 원인을 찾기 힘들었다.

문제는 새로운 테스트케이스를 시작할 때 벡터p[]를 초기화해주지 않아서 이전 테스트케이스에서 입력받았던 도로, 웜홀 연결들이 남아있었기 때문이었다.

한 문제에 테스트케이스 여러 개를 입력받아서 실행한다면 매 테스트케이스마다 사용하는 변수, 배열들을 초기화해줘야 한다는 것을 잊지 말자!

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 11404번 :: 플로이드  (0) 2019.12.20
BOJ 1541번 :: 잃어버린 괄호  (0) 2019.12.20
BOJ 11399번 :: ATM  (0) 2019.12.18
BOJ 1931번 :: 회의실 배정  (0) 2019.12.18
BOJ 11657번 :: 타임머신  (0) 2019.12.15

#문제

인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다.

사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1+4 = 8분이 필요하게 된다. 4번 사람은 3+1+4+3 = 11분, 5번 사람은 3+1+4+3+2 = 13분이 걸리게 된다. 이 경우에 각 사람이 돈을 인출하는데 필요한 시간의 합은 3+4+8+11+13 = 39분이 된다.

줄을 [2, 5, 1, 4, 3] 순서로 줄을 서면, 2번 사람은 1분만에, 5번 사람은 1+2 = 3분, 1번 사람은 1+2+3 = 6분, 4번 사람은 1+2+3+3 = 9분, 3번 사람은 1+2+3+3+4 = 13분이 걸리게 된다. 각 사람이 돈을 인출하는데 필요한 시간의 합은 1+3+6+9+13 = 32분이다. 이 방법보다 더 필요한 시간의 합을 최소로 만들 수는 없다.

줄을 서 있는 사람의 수 N과 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어졌을 때, 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)

출력

첫째 줄에 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력한다.

 

#작성 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <algorithm>
using namespace std;
 
int n;
int time[1001]={0,};
int main(){
    cin>>n;
    for(int i=1; i<=n; i++){
        cin>>time[i];
    }
    // 시간이 적게 걸리는 사람 순서대로 줄을 서야 한다. 
    sort(time, time+n+1);
    long long int sum=0;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=i; j++){
            sum +=time[j];
        }
    }
    cout<<sum;
    return 0;
}
cs

##

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 1541번 :: 잃어버린 괄호  (0) 2019.12.20
BOJ 1865번 :: 웜홀  (0) 2019.12.19
BOJ 1931번 :: 회의실 배정  (0) 2019.12.18
BOJ 11657번 :: 타임머신  (0) 2019.12.15
BOJ 11047번 :: 동전 0  (0) 2019.12.15

#문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의들에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의 수를 출력하여라.

 

#작성 코드

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 <vector>
#include <algorithm>
using namespace std;
 
int conf_n;
vector<pair<int, int> > conf;
bool comp( pair<int,int> a, pair<int,int> b){
    // 1순위 : 회의 끝 시간 오름차순
    // 2순위 : 회의 시작 시간 오름차순 
    if( a.second==b.second){
        return a.first<b.first;
    } 
    return a.second<b.second;
}
bool comp2( pair<int,int> a, pair<int,int> b){
    return a.first<b.first;
} 
int main(){
    cin>>conf_n;
    for(int i=1; i<=conf_n; i++){
        int start, end;
        cin>>start>>end;
        conf.push_back(make_pair(start, end));
    }
    // 회의 끝나는 시간 기준으로 오름차순 정렬 
    sort(conf.begin(), conf.end(), comp);
    int finTime = 0;
    int result=0;
    for(int i=0; i<conf_n; i++){
        // 이전회의 끝나는 시간 <= 새 회의 시작시간 
        if( finTime <= conf[i].first ){
            finTime = conf[i].second;
            result++;
        }
    }
    cout<<result<<'\n';
    return 0;
}
 cs

##

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 1865번 :: 웜홀  (0) 2019.12.19
BOJ 11399번 :: ATM  (0) 2019.12.18
BOJ 11657번 :: 타임머신  (0) 2019.12.15
BOJ 11047번 :: 동전 0  (0) 2019.12.15
BOJ 12865번 :: 평범한 배낭  (0) 2019.12.14

#문제

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C < 0인 경우는 타임머신으로 시간을 되돌아가는 경우이다.

1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. 

출력

만약 1번 도시에서 출발해 어떤 도시로 가는 과정에서 시간을 무한히 오래 전으로 되돌릴 수 있다면 첫째 줄에 -1을 출력한다. 그렇지 않다면 N-1개 줄에 걸쳐 각 줄에 1번 도시에서 출발해 2번 도시, 3번 도시, ..., N번 도시로 가는 가장 빠른 시간을 순서대로 출력한다. 만약 해당 도시로 가는 경로가 없다면 대신 -1을 출력한다.

 

#작성 코드

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
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
 
int n, m;
vector<pair<int, int> > city[501];        // city[1] ... city[500] 사용 
//city[i] -> B, time
int d[501];
int INF = 7000000;
 
void bellmanford(int start){
    // 시작 도시 제외한 다른 도시로 가는 시간 무한대로 초기화. 
    for(int i=1; i<=n; i++){
        d[i] = INF;
    }
    d[start] = 0;
 
    // dense graph를 가정하고 모든 노드간의 연결을 탐색한다. 
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            for(int k=0; k<city[j].size(); k++){
                int next = city[j][k].first;
                int connect = city[j][k].second;
                
                // d[j]가 INF가 아닐 때에만 간선 가중치와 더해서 업데이트 하는 것이 의미있다. 
                if( d[j]!=INF && d[next]>connect+d[j] ){
                    if( i==n ){
                        cout<<"-1\n";
                        return;
                    }
                    d[next] = connect + d[j];
                }
            }
        }
    }
    
    // 1번도시에서 출발해서 i번째 도시로 가는 최단거리 출력. 
    for(int i=2; i<=n; i++){
        if( d[i]>=5000000 ){
            cout<<"-1\n";
        }else{
            cout<<d[i]<<'\n';
        }
    }
    return;
}
 
int main(){
    cin>>n>>m;
    for(int i=0; i<m; i++){
        int start, dest, time;
        cin>>start>>dest>>time;
        city[start].push_back(make_pair(dest, time));
    }
    
    /* 벨만 포드 알고리즘 실행 */
    bellmanford(1);
    return 0;
} 
 cs

##

벨만 포드 알고리즘은 양의 가중치 간선만 허용하는 다익스트라 알고리즘과 달리 음의 값을 가지는 가중치 간선이 존재하는 그래프에서 단일 출발지 최단 경로를 구할 수 있는 알고리즘이다.

모든 노드와 노드 사이에 존재하는 간선을 탐색한다. (n-1번)

n-1번 Relaxing이 끝난 후, 한 번 더 Relaxing을 할 때 최단거리 업데이트가 발생한다면 음의 가중치 순환경로가 존재하는 것이므로 최단경로가 존재하지 않는다.

+) 굵게 표시한 부분, d[j]!=INF 일 때만 더 짧은 거리로 업데이트 하는것에 주의하자!

INF > INF-5 라고 해서 INF-5가 의미있는 최단거리는 아니다.

저 코드를 뺀 상태로 컴파일하면 어떤 테스트케이스에서 출력 초과가 발생한다.

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 11399번 :: ATM  (0) 2019.12.18
BOJ 1931번 :: 회의실 배정  (0) 2019.12.18
BOJ 11047번 :: 동전 0  (0) 2019.12.15
BOJ 12865번 :: 평범한 배낭  (0) 2019.12.14
BOJ 9370번 :: 미확인 도착지  (0) 2019.12.13

#문제

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

출력

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

 

#작성 코드

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 n,k;
int coinnum=0;
int coin[10];        //인덱스 1~10 사용
 
int main(){
    cin>>n>>k;
    for(int i=0; i<n; i++){
        cin>>coin[i];
    }
    
    for(int i=n-1; i>=0; i--){
        coinnum+=k/coin[i];
        k%=coin[i];
    }
    cout<<coinnum;
    return 0;
} 
 
 cs

##

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 1931번 :: 회의실 배정  (0) 2019.12.18
BOJ 11657번 :: 타임머신  (0) 2019.12.15
BOJ 12865번 :: 평범한 배낭  (0) 2019.12.14
BOJ 9370번 :: 미확인 도착지  (0) 2019.12.13
BOJ 1912번 :: 연속합  (0) 2019.12.09

+ Recent posts

티스토리툴바