제6회 천하제일 코딩대회 예선 Open Contest 후기

Yongjun Park·2022년 6월 10일

python 백준

CP(Competitive Programming)

목록 보기

3/19

대회 링크

A. 심준의 병역판정검사 : 구현 (브론즈 4)
B. 11월 11일 : 구현 (브론즈 3)
C. 순열 정렬 : 그리디 (실버 4)
D. 영어 시험 : 애드 혹 (실버 4)
E. 가장 긴 등차 부분 수열 : 다이나믹 프로그래밍 (골드 5)

결과 : A(7분) -> B(16분) -> D(33분) -> C(65분)
4/5솔

왠지 잘 풀리더라...
C번은 문제 이해하는 데 오래 걸려서 시간이 좀 걸렸다.

A번

표만 제대로 이해하면 바로 풀린다.
신장으로 1차 나누고, BMI 조건으로 2차 나누면 됨.

B번

m월 m일의 m일 전이 뭐냐?

10월 1일의 1일 전은 9월 30일이다.
10월 2일의 2일 전은 9월 30일이다.
...
10월 25일의 25일 전도 9월 30일이다.

즉, 저번 달의 마지막일을 출력하면 된다.

D번

애드 혹(Ad Hoc), 나무위키
반박이 나왔을 때 오직 이것에 대해서 반박하기 위해서만 필요한 가설. 임시방편.
즉, 문제에 대해 충분히 일반화되지 않은 해법인 셈.

애드 혹이라는 말은, 뭐... 그리디나 DP, Dijkstra처럼 일반화된 알고리즘을 사용하는 것이 아니라,
오로지 이번 문제를 풀 때에만 할 법한 독특한 생각을 해서 문제를 풀어야 한다는 것이다.

독특한 생각이라는 게 때로는 거창한 것이지만, 이번 문제에서는 전혀 아니다.

입력 : ba
출력 : abba
해설 : aa(abba), ab(abba), ba(abba), bb(abba) 를 모두 부분 수열로 갖는다.

사실 abba 말고 baba도 된다.

N = int(input())
print(input() * N)

..?
이런게 애드 혹이다.

C번

그리디라는 걸 알아채는 데 꽤 많은 시간이 걸렸다.

문제 중, 연산을 아무리 많이 사용해도 감소하지 않도록 만들 수 없는 순열이 존재한다. 라는 말을 이해하는 데 애먹었다.
질문을 해봤는데, "오름차순으로 만들 수 없는"으로 이해하시면 됩니다. 라는 답변을 받았다.

처음부터 오름차순으로 만들 수 없는 이라고 쓰던가...

5 2 3 4 1 -> YES
2 5 3 1 4 -> NO

왜 이렇게 되는지 이해해보자.

길이가 5면, 1<->5, 2<->4 , 3<->3으로 숫자 교체가 가능하다.
5 2 3 4 1을 1 2 3 4 5로 교체할 수 있으니 YES.
2 5 3 1 4는 기껏해야 2 1 3 5 4 밖에 안 되고, 오름차순으로는 절대 만들 수 없으니 NO다.

기껏해야..?
여기서 그리디의 냄새가 났다.
최대한 단조증가로 만들어 보고 중간에 무조건 안 되는 경우가 나오면 NO를 반환하는 식으로 풀었다.

처음에는 25182. 청정수열 (Hard) 문제와 흡사할 것이라는 생각에 지나치게 꽂혀서,
Pair 간의 꼬임 관계로 Y/N을 찾아낼 수 있을까하고 굉장히 고민했는데, 문제를 너무 과대평가한 것이었다.

import sys

def f(N, arr):
    for i in range(len(arr)):
        arr[i] = min(arr[i], N-arr[i]+1)
        if i == 0:
            continue
        if arr[i-1] > arr[i]:
            arr[i] = N-arr[i]+1
            if arr[i-1] > arr[i]:
                return False
    return True


T = int(sys.stdin.readline().rstrip())
for _ in range(T):
    N = int(sys.stdin.readline().rstrip())
    arr = list(map(int, sys.stdin.readline().rstrip().split()))
    print('YES' if f(N, arr) else 'NO')

E번 : 시간 초과

11053. 가장 긴 증가하는 부분 수열 문제에서 착안해서 시도해보았다.

# LIS(Longest Increasing Subsequence)

import sys

N = int(sys.stdin.readline().rstrip())
arr = list(map(int, sys.stdin.readline().rstrip().split()))
dp = [1] * N

for i in range(N):
    for j in range(i):
        if arr[j] < arr[i]: # 나보다 이전에 있는 작은 수를 발견하면
                            # 아, 나까지 이어서 +1 해도 되겠다 싶잖아
            dp[i] = max(dp[i], dp[j]+1) # 그런데 그 +1도 가장 긴 거에다가 더해야지
print(max(dp))

import sys

N = int(sys.stdin.readline().rstrip())
arr = list(map(int, sys.stdin.readline().rstrip().split()))

dp = [[1]*N for _ in range(199)]
OFFSET = 99

for i in range(N):
    for j in range(i):
        diff = arr[i] - arr[j] + OFFSET
        dp[diff][i] = max(dp[diff][i], dp[diff][j] + 1)

answer = 1
for y in range(199):
    for x in range(N):
        answer = max(answer, dp[y][x])
print(answer)