오늘의 코딩#22

오늘은 이사를 하기로 한 원룸이 나와서 계약을 하러 갔다.

원래는 방이 나오면 가능한 바로 갈 생각이었는데 42서울이 당분간 전면 비대면으로 전환이 되면서 그럴 필요성이 떨어졌다.

그래서 기왕 이렇게 된거 백신 2차 접종까지 마치고 가기로 하고 1월 말로 계약을 하고 왔다.

그리고 오랜만에 다시 백준을 풀었다.

지난번에 풀다가 계속 틀려서 포기했던 가장 긴 증가하는 부분 수열 문제에 이어서 2 문제를 풀었다.

가장 긴 증가하는 부분 수열 문제의 경우 {10, 20, 10, 30, 20, 50} 와 같이 입력을 받아 {10, 20, 30, 50}를 찾아 길이인 4를 출력 하는 문제이다.

확실히 오랜만에 풀어서 그런지 지난번에 어떻게 했는지 기억이 나지 않아 그냥 처음부터 다시 풀었다.

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
int n, i1, i2, max = 0;
int *data;
int *sequence;

scanf("%d", &n);
data = (int *)malloc(sizeof(int) * n);
sequence = (int *)malloc(sizeof(int) * n);
for (i1 = 0; i1 < n; i1++)
{
    scanf("%d", &data[i1]);
    sequence[i1] = 0;
    for (i2 = 0; i2 < i1; i2++)
        if (data[i1] > data[i2])
            sequence[i1] = sequence[i2] + 1 > sequence[i1] ? sequence[i2] + 1 : sequence[i1];
    max = max > sequence[i1] ? max : sequence[i1];
}
printf("%d\n", max + 1);
free(data);
free(sequence);
return (0);

}

그리 어려운 문제는 아니었다.

지난번에 왜 틀렸었는지 이해가 안 갈 정도였다.

그냥 전형적인 DP문제라 설명할 게 없다.

그 다음 문제는 가장 긴 바이토닉 부분 수열 문제다.

이 문제도 이전 문제와 큰 차이가 없다.

앞의 문제는 증가 만 해야 한다면 이 문제는 증가하다 감소하는 것을 허용한다.

가능한 동적할당을 하고 싶었는데 2차원 배열을 쓸 거라서 귀찮아서 그냥 배열 할당하고 풀었다.

#include <stdio.h>

int main(void)
{
int n, i1, i2, max = 0;
int data[1000];
int sequence[1000][2];

scanf("%d", &n);
for (i1 = 0; i1 < n; i1++)
{
    scanf("%d", &data[i1]);
    sequence[i1][0] = 0;
    sequence[i1][1] = 0;
    for (i2 = 0; i2 < i1; i2++)
    {
        if (data[i1] > data[i2])
            sequence[i1][0] = sequence[i2][0] + 1 > sequence[i1][0] ? sequence[i2][0] + 1 : sequence[i1][0];
        else if (data[i2] > data[i1])
        {
            if (sequence[i1][1] < sequence[i2][0] + 1)
                sequence[i1][1] = sequence[i2][0] + 1;
            if (sequence[i1][1] < sequence[i2][1] + 1)
                sequence[i1][1] = sequence[i2][1] + 1;
        }
    }
    max = max > sequence[i1][0] ? max : sequence[i1][0];
    max = max > sequence[i1][1] ? max : sequence[i1][1];
}
printf("%d\n", max + 1);
return (0);

}

이 문제는 앞 문제와 큰 차이가 없다.

그냥 값을 2개씩 저장한다 정도?

그냥 무난한 DP문제 였다.

오랜만에 문제를 풀어서 그런지 머리가 잘 돌아가는 것 같다.