#문제

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

 

2503번: 숫자 야구

첫째 줄에는 민혁이가 영수에게 몇 번이나 질문을 했는지를 나타내는 1 이상 100 이하의 자연수 N이 주어진다. 이어지는 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
#include <iostream>
using namespace std;
 
int n[101][3];        // t의 최대값이 100이므로 101을 사용. 
bool nums[1000];
 
int main(){
    int t, answer=0;
    fill_n(nums, 1000, true); 
    cin>>t;
    // t개의 입력을 받는다. 수, 스트라이크, 볼 
    for(int i=0; i<t; i++){
        cin>>n[i][0]>>n[i][1]>>n[i][2];
    }
    
    for(int num=123; num<=999; num++){ 
        int n1=num/100, n2=(num/10)%10, n3=num%10;
        // 숫자야구에서 발생할 수 없는 num에 대해서는 false 체크하고 다음 num으로 넘어간다.
        if( n1==0 || n2==0 || n3==0 || n1==n2 || n1==n3 || n2==n3 ){
            nums[num]=false;
            continue;
        }
        
        for(int i=0; i<t; i++){
            int x = n[i][0];
            int x1=x/100, x2=(x/10)%10, x3=x%10;
            int nowst=0, nowba=0;
            // 입력받은 x에 대해 strike, ball 판정 받는 케이스를 탐색.
            // 위치와 숫자가 같은 경우 strike 
            if( x1 == n1 ) nowst++;
            if( x2 == n2 ) nowst++;
            if( x3 == n3 ) nowst++;
            // 같은 숫자가 다른 위치에 있는 경우 ball 
            if( x1==n2 || x1==n3 ) nowba++;
            if( x2==n1 || x2==n3 ) nowba++;
            if( x3==n1 || x3==n2 ) nowba++;
             
            // 현재 입력에 대한 strike, ball개수와 탐색한 strike, ball개수가 동일하지 않다면 num은 가능성이 없는 숫자. 
            if( nowst!=n[i][1] || nowba!=n[i][2] ) {
                nums[num]=false;        // 현재 입력으로 가능성이 있는 수는 false체크 
            }
        }
    }
    
    for(int num=123; num<=999; num++){
        // 가능성이 있는 num의 개수를 센다. 
        if( nums[num]==true ) {
            answer++;
        }
    }
    cout<<answer<<'\n';
    return 0;
}
 
 cs

##

예제에서 주어진 수들을 탐색한 후에 324는 체크가 되었는데, 328이 체크가 안되어서 로직을 계속 살펴봤다.

결국 문제가 있던 부분은 ball을 판정하는 과정에서 x2==n1|| x2==n3이어야 하는데 x2대신 n2를 써놓고 왜 안되지? 하는 중이었다.

변수가 코드 속에 있을 때 한 눈에 잘 구분할 수 있도록 이름지어야겠다. n2와 x2는 너무 닮았어...

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 3078번 :: 좋은 친구  (0) 2020.02.10
BOJ 1182번 :: 부분수열의 합  (0) 2020.02.06
BOJ 10448번 :: 유레카 이론  (0) 2020.02.04
BOJ 3085번 :: 사탕 게임  (0) 2020.02.04
BOJ 2309번 :: 일곱 난쟁이  (0) 2020.02.03

#문제

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

 

10448번: 유레카 이론

문제 삼각수 Tn(n ≥ 1)는 [그림]에서와 같이 기하학적으로 일정한 모양의 규칙을 갖는 점들의 모음으로 표현될 수 있다. [그림] 자연수 n에 대해 n ≥ 1의 삼각수Tn는 명백한 공식이 있다. Tn = 1 + 2 + 3 + ... + n = n(n+1)/2 1796년, 가우스는 모든 자연수가 최대 3개의 삼각수의 합으로 표현될 수 있다고 증명하였다. 예를 들어, 4 = T1 + T2 5 = T1 + T1 + T2 6 = T2 + T2 or 6 = T

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
#include <iostream>
#include <vector>
using namespace std;
 
int t;
vector<int> tri;
 
int main(){
    cin>>t;
 
    // maxnum 이하의 삼각수까지를 계산해서 tri 벡터에 저장한다. 
    for(int i=1; i*(i+1)/2<1000; i++){
        tri.push_back(i*(i+1)/2);
    }
 
    for(int i=0; i<t; i++){
        int x;
        cin>>x;
        // 1000 이하의 삼각수의 개수가 적으므로 삼중 포문으로 해결할 수 있다.
        bool possible=false;
        for(int a=0; a<tri.size(); a++){
            for(int b=a; b<tri.size(); b++){
                for(int c=b; c<tri.size(); c++){
                    if(x==tri[a]+tri[b]+tri[c]){
                        cout<<"1\n";
                        possible = true;
                    }
                    if( possible ) break;
                }
                if( possible ) break;
            }
            if( possible ) break;
        }
        if(!possible) cout<<"0\n";
    }
    
    return 0; 
}
 cs

##

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 1182번 :: 부분수열의 합  (0) 2020.02.06
BOJ 2503번 :: 숫자 야구  (0) 2020.02.06
BOJ 3085번 :: 사탕 게임  (0) 2020.02.04
BOJ 2309번 :: 일곱 난쟁이  (0) 2020.02.03
BOJ 16500번 :: 문자열 판별  (0) 2020.02.03

#문제

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

 

3085번: 사탕 게임

문제 상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다. 가장 처음에 N×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
#include <iostream>
using namespace std;
 
int n;
char candy[50][50];
int maxCandy=0;
 
void swap(char &a, char &b){
    char tmp = a;
    a = b;
    b = tmp;
}
 
void seq(){
    // candy[][] 전체에서 최대 연속부분의 원소 개수를 maxCandy에 저장한다.
    
    // 가로 연속부분 탐색
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            int cnt=1;
            for(int k=j+1; k<n; k++){
                if( candy[i][j]==candy[i][k] ){
                    cnt++;
                }
                else{
                    maxCandy = max(maxCandy, cnt);
                    break;
                }
                if( k==n-1 ) maxCandy = max(maxCandy, cnt);
                // 행의 끝까지 연속되면 else로 진입하지 않기때문에 필요한 부분. 
            }
        }
    } 
    
    // 세로 연속부분 탐색
    for(int j=0; j<n; j++){
        for(int i=0; i<n; i++){
            int cnt=1;
            for(int k=i+1; k<n; k++){
                if(candy[i][j]==candy[k][j]){
                    cnt++;
                }
                else{
                    maxCandy = max(maxCandy, cnt);
                    break;
                }
                if( k==n-1 ) maxCandy = max(maxCandy, cnt);
                // 열의 끝까지 연속되면 else로 진입하지 않기때문에 필요한 부분.
            }
        }
    } 
}
 
int main(){
    cin>>n;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin>>candy[i][j];
        }
    }
    
    // 가로로 연결된 두 개를 교환하는 경우
    for(int i=0; i<n; i++){
        for(int j=0; j<n-1; j++){
            swap(candy[i][j], candy[i][j+1]);
            // 최대 연속 부분 탐색. 최대 연속부분 개수를 maxCandy에 저장 
            seq();
            swap(candy[i][j], candy[i][j+1]);
        }
    }
    // 세로로 연결된 두 개를 교환하는 경우 
    for(int j=0; j<n; j++){
        for(int i=0; i<n-1; i++){
            swap(candy[i][j], candy[i+1][j]);
            // 최대 연속 부분 탐색. 최대 연속부분 개수를 maxCandy에 저장
            seq();
            swap(candy[i][j], candy[i+1][j]);
        }
    }
    cout<<maxCandy<<'\n';
    return 0;
}
 cs

##

어떻게 풀기는 했는데, 시간 복잡도가 아주 큰 코드가 아닐까...??

이게 최선인가....? 최적화가 필요해보인다.

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 2503번 :: 숫자 야구  (0) 2020.02.06
BOJ 10448번 :: 유레카 이론  (0) 2020.02.04
BOJ 2309번 :: 일곱 난쟁이  (0) 2020.02.03
BOJ 16500번 :: 문자열 판별  (0) 2020.02.03
BOJ 11052번 :: 카드 구매하기  (0) 2020.02.03

#문제

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

 

2309번: 일곱 난쟁이

아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 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
#include <iostream>
#include <algorithm>
using namespace std;
 
int tall[9];
int sum=0;
 
int main(){
    for(int i=0; i<9; i++){
        cin>>tall[i];
        sum+=tall[i];
    }
    
    sort(tall, tall+9);
    for(int i=0; i<9; i++){
        for(int j=i+1; j<9; j++){
            if( sum-tall[i]-tall[j]==100 ){
                for(int k=0; k<9; k++){
                    if ( k==i || k==j ) continue;
                    cout<<tall[k]<<'\n';
                }
                return 0;        // 답이 여러개일 때 하나만 출력해야하므로 
            }
        }
    }
}
 cs

##

아홉 난쟁이들의 키를 입력받으면서 sum에 모두 더해놓고,

아홉 난쟁이들의 키를 오름차순으로 정렬한다.

그 중 중복되지않도록 두 개를 골라 sum에서 키를 뺐을 때 100이 된다면 그 두개를 제외한 키를 출력하고, return 0;으로 메인 함수를 종료한다.

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 10448번 :: 유레카 이론  (0) 2020.02.04
BOJ 3085번 :: 사탕 게임  (0) 2020.02.04
BOJ 16500번 :: 문자열 판별  (0) 2020.02.03
BOJ 11052번 :: 카드 구매하기  (0) 2020.02.03
BOJ 1699번 :: 제곱수의 합  (0) 2020.02.02

#문제

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

 

16500번: 문자열 판별

첫째 줄에 길이가 100이하인 문자열 S가 주어진다. 둘째 줄에는 A에 포함된 문자열의 개수 N(1 ≤ N ≤ 100)이 주어진다. 셋째 줄부터 N개의 줄에는 A에 포함된 단어가 한 줄에 하나씩 주어진다. A에 포함된 문자열은 알파벳 소문자로만 이루어져 있고, 길이는 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
53
54
#include <iostream>
#include <vector>
using namespace std;
 
string s;
int n;        // word의 개수. 
vector<string> word;
    
bool works(int idx){
    // s의 끝에 도달하면 true를 리턴한다. 
    if( idx==s.length() ){
        return true;
    }
    
    // s의 idx에서부터 word에 존재하는 단어 하나하나를 매칭시켜본다. 
    for(int i=0; i<n; i++){
        bool flag = true;
        
        // word[i]의 길이를 idx에 더했을 때 s의 길이를 벗어나면 이 문자는 비교하지않는다. 
        if( idx+word[i].length() > s.length() ) continue;
        
        // s의 idx부터 word[i]를 문자 하나하나 비교한다. 
        for(int ii=0; ii<word[i].length(); ii++){
            if( s[idx+ii] != word[i][ii] ){
                flag = false;
                break;    // 이 word는 매칭되지않으므로 break하고 다음 문자 매칭으로 넘어간다. 
            }
        }
        
        if( flag ){
            // word[i]로 s를 구성할 수 있다면 그 이하의 s의 대해서 재귀적으로 가능한지 검사한다.
            if( works(idx+word[i].length()) ) return true;
        }
    }
    return false;
} 
 
int main(){
    cin>>s;
    cin>>n;
    for(int i=0; i<n; i++){
        string x;
        cin>>x;
        word.push_back(x);
    }
    
    if( works(0)==true ){
        cout<<"1\n";
    }
    else{
        cout<<"0\n";
    }
    return 0;
}
 cs

##

s의 idx에서부터 각 word에 대해 매칭 검사를 하고,

포함되는 word가 있다면 해당 word의 길이만큼 idx에 더해서 그 위치부터 각 word에 대해 다시 매칭 검사를 한다.

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 3085번 :: 사탕 게임  (0) 2020.02.04
BOJ 2309번 :: 일곱 난쟁이  (0) 2020.02.03
BOJ 11052번 :: 카드 구매하기  (0) 2020.02.03
BOJ 1699번 :: 제곱수의 합  (0) 2020.02.02
BOJ 9465번 :: 스티커  (0) 2020.02.02

#문제

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

 

11052번: 카드 구매하기

첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)

www.acmicpc.net

 

#작성 코드

TOP-DOWN

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
#include <iostream>
using namespace std;
 
int n;
int cards[1001];
int dp[1001];
 
int buy(int n){
    if( n==0 ){
        return 0;
    }
    if( dp[n]!=0 ){
        return dp[n];
    }
    
    for(int i=1; i<=n; i++){
        dp[n] = max(dp[n], buy(n-i)+cards[i]);
    }
    return dp[n];
    
}
int main(){
    cin>>n;
    for(int i=1; i<=n; i++){
        cin>>cards[i];
    }
    
    cout<<buy(n)<<'\n';
    return 0;
}
 cs

BOTTOM-UP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;
 
int n;
int cards[1001];
int dp[1001];        // dp[i] : i개 카드 구매할 수 있는 최대 지불 금액 
 
int main(){
    cin>>n;
    for(int i=1; i<=n; i++){
        cin>>cards[i];
    }
    
    for(int i=1; i<=n; i++){
        for(int j=1; j<=i; j++){
            dp[i] = max(dp[i], dp[i-j]+cards[j]);
        }
    }
    
    cout<<dp[n]<<'\n';
    return 0;
}
 cs

##

https://ldgeao99.tistory.com/m/288 참고!!!

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 2309번 :: 일곱 난쟁이  (0) 2020.02.03
BOJ 16500번 :: 문자열 판별  (0) 2020.02.03
BOJ 1699번 :: 제곱수의 합  (0) 2020.02.02
BOJ 9465번 :: 스티커  (0) 2020.02.02
BOJ 2618번 :: 경찰차  (0) 2020.02.01

+ Recent posts

티스토리툴바