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)
    # ///////////////////////////////////////////////////////////////////////////////////

4615. 재미있는 오셀로 게임 D3

8방향에 대해서 푸는 문제이다.

정말 오랜만이라 상기시켜 볼려고 글 씀.

dx = [0, 1, 1, 1, 0, -1, -1, -1]
dy = [1, 1, 0, -1, -1, -1, 0, 1]

로 방향을 관리하는게 핵심임.

비슷한 문제로 

https://www.hackerrank.com/challenges/queens-attack-2/problem

가 있었다.

from collections import deque
import sys

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

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

    board = [[0] * (N+1) for _ in range(N+1)]

    for i in range(N+1):
        board[0][i] = 3
        board[i][0] = 3

    # 1 이 흑. 2 가 백.
    board[N//2][N//2] = 2
    board[N // 2][(N // 2)+1] = 1
    board[(N // 2)+1][N // 2] = 1
    board[(N // 2)+1][(N // 2)+1] = 2

    # print(*board,sep='\n')

    # 아래, 우측아래, 우측, 우측위, 위, 좌측위, 좌측, 좌측아래
    dx = [0, 1, 1, 1, 0, -1, -1, -1]
    dy = [1, 1, 0, -1, -1, -1, 0, 1]

    Q = deque()

    for _ in range(M):
        c, r, color = map(int, input().split())
        board[r][c] = color
        if color == 1:
            for d in range(8):
                x, y = c, r
                x += dx[d]
                y += dy[d]
                while 1 <= x <= N and 1 <= y <= N:
                    if board[y][x] == 2:
                        Q.append((x,y))
                    if board[y][x] == 1:
                        while Q:
                            x, y = Q.pop()
                            board[y][x] = 1
                        break
                    if board[y][x] == 0 or board[y][x] == 3:
                        break
                    x += dx[d]
                    y += dy[d]
                Q.clear()
        if color == 2:
            for d in range(8):
                x, y = c, r
                x += dx[d]
                y += dy[d]
                while 1 <= x <= N and 1 <= y <= N:
                    if board[y][x] == 1:
                        Q.append((x,y))
                    if board[y][x] == 2:
                        while Q:
                            x, y = Q.pop()
                            board[y][x] = 2
                        break
                    if board[y][x] == 0 or board[y][x] == 3:
                        break
                    x += dx[d]
                    y += dy[d]
                Q.clear()
        # board[r][c] = color
        # print(r,c,color)
        # print(*board, sep='\n')

    # print()
    # print(*board,sep='\n')
    bc = 0
    wc = 0
    for i in range(1,N+1):
        for j in range(1,N+1):
            if board[i][j] == 1: bc += 1
            if board[i][j] == 2: wc += 1


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