1. 가장 큰 증가 수열

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

구현

• 그냥 구하면 된다.

문제점
1. 가장 작은 증가수열인 길이 1인 증가수열을 생각했어야 했다.
따라서 dp[i] = arr[i]로 초기화 했어야만 했다.

    for(int i=1;i<=N;i++)
    {   
        cin >> arr[i];
        dp[i] = arr[i]; // dp를 본인의 값으로 초기화 해주는게 필요
    }
    
    //DP
    for(int i=1;i<N;i++)
    {
        for(int j=i+1; j<=N; j++)
        {
            if(arr[i] < arr[j])
            {
                dp[j] = max(dp[j], dp[i] + arr[j]);
            }
        }
    }

2. 가장 긴 감소 수열

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

구현

• 그냥 하면 된다.

    for(int i=1;i<N;i++)
    {
        for(int j=i+1; j<=N; j++)
        {
            if(arr[i] > arr[j])
            {
                dp[j] = max(dp[i] + 1, dp[j]);
            }
        }
    }

문제점

• 없

3. 가장 긴 바이토닉 수열

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

구현

• 가장 긴 증가수열, 감소수열을 풀었다면, 어렵지 않았을 문제
• 아래처럼 풀면 된다.

문제점

• 결과에 -1하는 것을 바로 생각하지 못했다.

#include <iostream>
#include <cstring>

using namespace std;

int dp[1001][2];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N;
    cin >> N;

    int arr[N + 1] = {
        0,
    };
    for (int i = 1; i <= N; i++)
    {
        cin >> arr[i];

        for (int k = 0; k < 2; k++)
        {
            dp[i][k] = 1;
        }
    }

    // 정방향으로 증가수열
    for(int i=1; i<N; i++)
    {
        for(int j=i+1; j<=N; j++)
        {
            if(arr[i] < arr[j])
            {
                dp[j][0] = max(dp[j][0], dp[i][0] + 1);
            }
        }
    }

    // 역방향으로 감소수열
    for(int i=N; i>1; i--)
    {
        for(int j=i-1; j>=1; j--)
        {
            if(arr[i] < arr[j])
            {
                dp[j][1] = max(dp[j][1], dp[i][1] + 1);
            }
        }
    }

    
    int result = 0;
    for (int i = 1; i <= N; i++)
    {
        result = max(dp[i][0] + dp[i][1], result);
    }
    cout << result - 1; // 중복된 부분 제외

    return 0;
}

4. 연속합 +

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

어떻게 하나만 생략하게 할 수 있지??

https://www.acmicpc.net/board/view/21999
https://www.acmicpc.net/board/view/50542
스킵..

아래도 일단 스킵

타일 채우기 +
https://www.acmicpc.net/problem/2133
RGB거리2
https://www.acmicpc.net/problem/17404

5. 7 난쟁이 키 100

구현

• 브루트포스답게 무작정 구하면 됨.
• 브루트포스를 사용할 수 있던 이유는 입력이 9로 고정이어서.

문제점
1. 왜인지 풀기가 쉽지 않았다.

• set을 사용했다.

#include <iostream>
#include <set>

using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int arr[9];

    int result = 0;
    for(int i=0;i<9;i++)
    {
        cin >> arr[i];
        result += arr[i];
    }

    int a=0, b=0;
    for(int i=0;i<9;i++)
    {
        for(int j=0;j<9;j++)
        {
            if(result - (arr[i]+arr[j]) == 100)
            {
                a = i;
                b = j;
                break;
            }
        }

        if(a!=b)
        {
            break;
        }
    }

    set<int> s;
    for(int i=0;i<9;i++)
    {
        if(i==a || i==b)
        {
            continue;
        }
        else
        {
            s.insert(arr[i]);
        }
    }

    for(auto a : s)
    {
        cout << a << "\n";
    }

return 0;   
}

6. 사탕게임

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

구현

• 실패
• 어떻게 하는지는 알겠는데,
  map에 브루트포스를 하니 굉장히 구현이 더러워진다.

문제점

• https://www.acmicpc.net/board/view/74457
  유일하게 틀린 반례

1. 위아래로 교환할 때, 그 행에서의 최대길이를 구했고,
   왼오로 교환할 때, 그 열에서의 최대길이를 구했었는데,

그냥 교환하면 2차원 배열에서의 모든 최대 길이를 구해야한다.

스킵.

7. 날짜 계산

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

구현

• 그냥 지문대로 구현하면 된다.

문제점
1. 처음에 나머지로 풀려고 했다.
하지만 안되는 방법이라는 것을 깨달았는데, 그 이유가
1~15까지만 표현할 수 있는데
%15는 0~14까지만 표현할 수가 있다.

이 방식의 차이로 인해서 0이 나올때, 15가 나올때
일일이 조건문을 붙이기보다 그냥 푸는게 간단했다.

 if(te>15)
        {
            te-=15;
        }

        if(ts>28)
        {
            ts-=28;
        }

        if(tm>19)
        {
            tm-=19;
        }

        num++;

while문 내부에서 위처럼 돌면 된다. (일부분만 작성한 것)

8. 수 이어쓰기

12345678910111213 ...
https://www.acmicpc.net/problem/1748

구현

• 구현은 생각하는대로 구현하면 되었다.
• 어려운 부분은 자릿수, 규칙들이었다.

    // 10^0 1~9는 9*1 = 9자리
    // 10^1 10~99는 90*2 = 180자리
    // 10^2 100~999는 900*3 = 2700자리
    // 10^3 9000,4... 10^4 90000,5...

이런식으로 적어두고 푸니 구현하기 쉬웠다.

문제점
1. 문제를 더럽게 풀었다.
사용해야 할 변수를 그때그때 while문 돌리고 만들어서 사용했다.