3307. 최장 증가 부분 수열 D3

 예전에 완전히 같은 문제가 있었는데도 기억이 안났어서 상기시키기 위해 올림.

또 문제 조건 잘 보자. 런타임 에러 계속 떠서 왜 안되나 몰랐다.

import sys

sys.stdin = open("sample_input3.txt", "r")

### https://wayhome25.github.io/cs/2017/04/15/cs-16/
def binary_search(target):
    # data.sort()
    start = 0
    end = len(C) - 1

    while start <= end:
        mid = (start + end) // 2

        if C[mid] <= target:
            start = mid + 1
        else:
            end = mid -1

    return start

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    # ///////////////////////////////////////////////////////////////////////////////////
    # 파이썬 SW문제해결 응용_최적화 - 04 동적계획법의 활용
    # 알고보니 5262. [파이썬 S/W 문제해결 최적화] 4일차 - 정렬된 부분 집합 D4 와 같은문제...
    N = int(input())
    numbers = list(map(int, input().split()))

    C = [2**31] * (N+1)
    C[0] = 0
    LIS = [1] * N

    c_index = 0
    for i,n in enumerate(numbers):
        c_index = binary_search(n)
        C[c_index] = n
        LIS[i] = c_index
        # print("i :",i,", n :",n, ", c_index :",c_index)
        # print("C :",C)
        # print("LIS :",LIS)

    print("#{}".format(test_case), max(LIS))
    # ///////////////////////////////////////////////////////////////////////////////////

1860. 진기의 최고급 붕어빵 D3

사람생각으로 푸는게 잘못 되었다는걸 상기시키기 위해 올린다.

좀더 컴퓨터 적으로 머리를 굴려야 하는데.. 그게 잘 안된다.

모범적인 답안은 해당 사이트에 들어가 포인트를 소비하며 보자..

import sys

sys.stdin = open("input2.txt", "r")


T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    # ///////////////////////////////////////////////////////////////////////////////////
    N, M, K = map(int, input().split())

    customers = sorted(list(map(int, input().split())))

    bbang = 0

    customer_index = 0

    result = "Possible"
    if min(customers) == 0:
        result = "Impossible"
    else:
        for time in range(1, max(customers)+1):
            if time % M == 0:
                bbang += K
            while customers[customer_index] == time:
                bbang -= 1
                customer_index += 1
                if bbang < 0:
                    result = "Impossible"
                    break
                if customer_index == N:
                    break


    print("#{}".format(test_case),result)
    # ///////////////////////////////////////////////////////////////////////////////////

2817. 부분 수열의 합 D3

부분수열이라고 하지만 부분집합 문제다.

처음엔 생각나는대로 문제를 풀고, 알고보니 전 강의 실습에 있던거랑 같은 문제라서 그때 사용한 방법을 이용함(https://lightsg2.blogspot.com/2020/05/5260-sw-3.html)

다 사용해서 각각 걸린 시간 비교용과 직관과 배움의 차이?

전에 비트마스크 문제를 풀었기 때문에 이것도 알아두자.

import sys

sys.stdin = open("sample_input.txt", "r")

def allPartSum(i,K,S,R):
    global result
    if i == -1:
        if S == K:
            result += 1
        return
    if S > K: return
    if R < K: return
    allPartSum(i - 1, K, S + numbers[i], R)
    allPartSum(i - 1, K, S,R - numbers[i])

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    # ///////////////////////////////////////////////////////////////////////////////////
    N, K = map(int, input().split())
    numbers = list(map(int, input().split()))

    result = 0
    # 시간 초과
    # for i in range(1 << len(numbers)):
    #     if sum([numbers[j] for j in range(len(numbers)) if i & (1 << j)]) == K: result += 1

    # 4,138 ms
    # for i in range(1 << len(numbers)):
    #     temp_sum = 0
    #     for j in range(len(numbers)):
    #         if i & (1 << j):
    #             temp_sum += numbers[j]
    #         if temp_sum > K: break # 2,197 ms
    #     if temp_sum == K: result += 1
    #     temp_sum = 0

    # 626 ms
    allsum = sum(numbers)
    allPartSum(N-1,K,0,allsum)

    print("#{}".format(test_case), result)
    # ///////////////////////////////////////////////////////////////////////////////////