문제 링크

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

 

11053번: 가장 긴 증가하는 부분 수열

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

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
#include <iostream>
#include <cstdio>
#include <algorithm>
 
using namespace std;
 
int main(void) {
    int N;
    int min = 0;
    int max = 0;
    int arr[1001] = { 0 };
    int dp[1001] = { 0 };
 
    cin >> N;
 
    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
    }
 
    for (int i = 1; i <= N; i++) {
        min = 0;
        for (int j = 1; j <= i; j++) {
            if (arr[i] > arr[j]&&dp[j]>min) {
                min = dp[j];
            }
        }
        dp[i] = min + 1;
        if (max < dp[i]) {
            max = dp[i];
        }
    }
    cout << max << '\n';
}
 cs
 

[백준][11053번][DP] 가장 긴 증가 부분 수열

가장 긴 증가 부분 수열 https://www.acmicpc.net/problem/11053 <코드> 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 #include int main(void){ int N; int Dp[10..

wootool.tistory.com

  • i번째 숫자까지의 증가 부분 수열 개수를 기록하며 조사하고 가장 많은 수열의 개수를 출력한다.
  • 중간에 매우 큰 값이 나올 수 있으므로 조건문에 dp의 값도 비교하면서 최대한으로 나올 수 있는 경우의 수를 구한다.

코드 채점 결과

저작자표시 (새창열림)

'BAEKJOON' 카테고리의 다른 글

[BaekJoon]11722번 - 가장 긴 감소하는 부분 수열(DP)  (0) 2019.08.06
[BaekJoon]11055번 - 가장 큰 증가 부분 수열(DP)  (0) 2019.08.06
[BaekJoon]9012번 - 괄호  (0) 2019.08.03
[BaekJoon]10828번 - 스택  (0) 2019.08.03
[BaekJoon]11004번 - K번째 수(정렬)  (0) 2019.08.02

문제 링크

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

 

9012번: 괄호

문제 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(conc

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 <cstdio>
#include <string>
 
using namespace std;
 
int main() {
    int T;
    cin >> T;
 
    for (int i = 0; i < T; i++) {
        int cnt = 0;
        string tmp;
        cin >> tmp;
        for (int j = 0; j < tmp.length(); j++) {
            char tmp2 = tmp.at(j);
            if (tmp2 == '(') {
                cnt++;
            }
            else if (tmp2 == ')') {
                cnt--;
                if (cnt < 0) {
                    cout << "NO" << "\n";
                    break;
                }
            }
        }
        if (cnt == 0) {
            cout << "YES\n";
        }
        else if(cnt > 0){
            cout << "NO\n";
        }
    }
}
 cs
  • string의 기능 중 하나인 string.at(index)를 사용하여 비교했다.
  • cnt를 선언하고 '('가 나오면 +1, ')'가 나오면 -1을 해주었다.
  • 여기서 '(' (+1)가 나오지 않은 상태(0)에서 바로 ')' (-1)가 나온다면 그것은 성립할 수 없으므로 바로 "NO"를 출력하고 다음으로 넘어간다.
  • 마지막 괄호까지 카운트한 후 cnt값이 0이 되었다면 "YES"를 출력하고 나머지는 모두 "NO"를 출력한다.

코드 채점 결과

저작자표시 (새창열림)

'BAEKJOON' 카테고리의 다른 글

[BaekJoon]11055번 - 가장 큰 증가 부분 수열(DP)  (0) 2019.08.06
[BaekJoon]11053번 - 가장 긴 증가하는 부분 수열(DP)  (0) 2019.08.04
[BaekJoon]10828번 - 스택  (0) 2019.08.03
[BaekJoon]11004번 - K번째 수(정렬)  (0) 2019.08.02
[BaekJoon]2156번 - 포도주 시식(점화식 dp)  (0) 2019.08.02

내가 작성한 코드

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
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
 
using namespace std;
 
int main(void) {
    int N,tmp;
    vector <int> arr;
    string S;
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        cin >> S;
        if (!S.compare("push")) {
            cin >> tmp;
            arr.push_back(tmp);
        }
        else if (!S.compare("pop")) {
            if (arr.empty()) {
                printf("-1\n");
            }
            else {
                printf("%d\n", arr.back());
                arr.pop_back();
            }
        }
        else if (!S.compare("size")) {
            printf("%d\n", arr.size());
        }
        else if (!S.compare("empty")) {
            printf("%d\n", arr.empty());
        }
        else if (!S.compare("top")) {
            if (arr.empty()) {
                printf("-1\n");
            }
            else {
                printf("%d\n", arr.back());
            }
        }
    }
}
 cs
  • compare을 이용하여 명령어를 판단하고 조건에 따라 나누어 작성하였다.

코드 채점 결과

저작자표시 (새창열림)

'BAEKJOON' 카테고리의 다른 글

[BaekJoon]11053번 - 가장 긴 증가하는 부분 수열(DP)  (0) 2019.08.04
[BaekJoon]9012번 - 괄호  (0) 2019.08.03
[BaekJoon]11004번 - K번째 수(정렬)  (0) 2019.08.02
[BaekJoon]2156번 - 포도주 시식(점화식 dp)  (0) 2019.08.02
[BaekJoon]11652번 - 카드  (0) 2019.08.01

내가 작성한 코드

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 <cstdio>
#include <map>
#include <algorithm>
 
using namespace std;
 
int main(void) {
    int N,K;
    int arr[5000000];
    
    scanf("%d", &N);
    scanf("%d", &K);
 
    for (int i = 0; i < N; i++) {
        scanf("%d", &arr[i]);
    }
 
    sort(arr, arr + N);
 
    printf("%d\n", arr[K - 1]);
}
 cs
  • stack overflow가 발생하는 경우 프로젝트의 속성 -> 링커 -> 시스템 -> 스택 예약 크기에 100MB(100 * 1024 * 1024) 정도로 바꾸면 된다.

코드 채점 결과

저작자표시 (새창열림)

'BAEKJOON' 카테고리의 다른 글

[BaekJoon]9012번 - 괄호  (0) 2019.08.03
[BaekJoon]10828번 - 스택  (0) 2019.08.03
[BaekJoon]2156번 - 포도주 시식(점화식 dp)  (0) 2019.08.02
[BaekJoon]11652번 - 카드  (0) 2019.08.01
[BaekJoon]10989번 - 수 정렬하기 3  (0) 2019.08.01

내가 작성한 코드

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
#include <iostream>
#include <cstdio>
#include <algorithm>
 
using namespace std;
 
int main(void) {
    int n;
    int W[10001] = { 0 };
    int dp[10001] = { 0 };
 
    scanf("%d",&n);
    
    for (int i = 1; i <= n; i++) {
        scanf("%d", &W[i]);
    }
 
    dp[1] = W[1];
    dp[2] = W[1]+W[2];
 
    for (int i = 3; i <= n; i++) {
        int result = max(W[i] + dp[i - 2], W[i] + W[i - 1] + dp[i - 3]);
        result = max(result, dp[i - 1]);
        dp[i] = result;
    }
    
    printf("%d\n", dp[n]);
}
 cs
  • dp를 비교하는 방식
  1. n번째 와인을 마시고 n-2번째까지의 와인을 마셨을 때 가장 많은 와인을 마신 경우
  2. n번째 와인과 n-1번째 와인을 마시고 n-3번째까지의 와인을 마셨을 때 가장 많은 와인을 마신 경우
  3. n번째 와인을 마시지 않고 n-1번째까지의 와인을 마셨을 때 가장 많은 와인을 마신 경우
  • 위 3가지 경우의 수 중에서 가장 큰 경우를 선택하면 된다.

코드 채점 결과

저작자표시 (새창열림)

'BAEKJOON' 카테고리의 다른 글

[BaekJoon]10828번 - 스택  (0) 2019.08.03
[BaekJoon]11004번 - K번째 수(정렬)  (0) 2019.08.02
[BaekJoon]11652번 - 카드  (0) 2019.08.01
[BaekJoon]10989번 - 수 정렬하기 3  (0) 2019.08.01
[BaekJoon]9465번 - 스티커  (0) 2019.07.31

내가 작성한 코드

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
 
using namespace std;
 
int main(void) {
    int N;
    int max = 0;
    int cnt = 0;
    long long tmp;
    map <long long, int> arr;
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        scanf("%lld", &tmp);
 
        arr[tmp]++;
    }
 
    for (auto i = arr.begin(); i != arr.end(); i++) {
        if (i->second > max) {
            max = i->second;
            tmp = i->first;
        }
    }
    printf("%lld", tmp);
}
 cs
  • map을 사용하여 풀 수 있었다.
  • 범위가 매우 넓었고 순서도 뒤죽박죽에 음수 값도 넣어야 했기에 기존에 사용하던 방식으로는 해결할 수 없었다.
  • map을 사용하면 first값에 key, second값에 value를 넣어 first값에 따라 알아서 정리가 되었다.
  • 그 후에 map의 처음부터 마지막 값까지 비교하며 가장 많이 입력된 값을 저장하여 출력했다.

코드 채점 결과

저작자표시 (새창열림)

'BAEKJOON' 카테고리의 다른 글

[BaekJoon]11004번 - K번째 수(정렬)  (0) 2019.08.02
[BaekJoon]2156번 - 포도주 시식(점화식 dp)  (0) 2019.08.02
[BaekJoon]10989번 - 수 정렬하기 3  (0) 2019.08.01
[BaekJoon]9465번 - 스티커  (0) 2019.07.31
[BaekJoon]2193번 - 이친수  (0) 2019.07.30

내가 작성한 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <cstdio>
 
using namespace std;
 
int main(void) {
    int N,tmp;
    int arr[10001] = { 0 };
    cin >> N;
    for (int i = 1; i <= N; i++) {
        scanf("%d", &tmp);
        arr[tmp]++;
    }
 
    for (int i = 1; i <= 10000; i++) {
        for (int j = 0; j < arr[i]; j++) {
            printf("%d\n",i);
        }
    }
}
 cs
  • 기존의 방식대로 작성해 보았으나 너무 오래 걸리고 메모리도 많이 차지했기 때문에 다른 방법을 찾아보았다.
  • 10000개의 숫자가 얼마나 반복되었는지 count를 세고, 순차적으로 그 개수만큼 출력하게 했다.
  • 또한 cin과 cout을 사용해도 시간 초과가 발생했다.
  • cin -> scanf, cout -> printf

코드 채점 결과

저작자표시 (새창열림)

'BAEKJOON' 카테고리의 다른 글

[BaekJoon]2156번 - 포도주 시식(점화식 dp)  (0) 2019.08.02
[BaekJoon]11652번 - 카드  (0) 2019.08.01
[BaekJoon]9465번 - 스티커  (0) 2019.07.31
[BaekJoon]2193번 - 이친수  (0) 2019.07.30
[BaekJoon]11057번 - 오르막 수  (0) 2019.07.30

 

9465번: 스티커

문제 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 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
#include <iostream>
 
using namespace std;
 
int max(int a, int b) {
    if (a > b) {
        return a;
    }
    return b;
}
 
int main(void) {
    int T;
    int n;
    cin >> T;
    int ans[100001];
 
    for (int i = 0; i < T; i++) {
        int s[2][100001] = { 0 };
        int dp[2][100001] = { 0 };
        cin >> n;
        for (int z = 0; z < 2; z++) {
            for (int j = 1; j <= n; j++) {
                cin >> s[z][j];
            }
        }
        dp[0][1] = s[0][1];
        dp[1][1] = s[1][1];
 
        for (int j = 2; j <= n; j++) {
            dp[0][j] = max(dp[1][j - 1], dp[1][j - 2]) + s[0][j];
            dp[1][j] = max(dp[0][j - 1], dp[0][j - 2]) + s[1][j];
        }
        ans[i] = max(dp[0][n], dp[1][n]);
    }
    for (int i = 0; i < T; i++) {
        cout << ans[i] << '\n';
    }
}
 cs
 

[백준 BOJ][DP] 9465 스티커

9465_스티커 링크 https://www.acmicpc.net/problem/9465 풀이 만약 별에서 시작했다면 1이나 2를 갈 수 있습니다. 하지만 2는 1을 거쳤다 갈 수 있기 때문에 1로 가야합니다. 이 상황도 마찬가지로 1로 가는..

jaemin8852.tistory.com

  • 점수를 저장할 dp배열을 스티커 점수 배열과 동일한 크기로 선언하여 더 큰 점수의 경우의 수를 선택하여 더해간다.
  • 한 칸 전, 두 칸 전 중 어떤 것이 더 점수가 높은지 비교하면 된다.

코드 채점 결과

 

저작자표시 (새창열림)

'BAEKJOON' 카테고리의 다른 글

[BaekJoon]11652번 - 카드  (0) 2019.08.01
[BaekJoon]10989번 - 수 정렬하기 3  (0) 2019.08.01
[BaekJoon]2193번 - 이친수  (0) 2019.07.30
[BaekJoon]11057번 - 오르막 수  (0) 2019.07.30
[BaekJoon]10825번 - 국영수  (0) 2019.07.30

+ Recent posts

티스토리툴바