[DP+DFS/BFS] 1012번, 9465번, 18353번

1. 병사 배치하기

코드

import sys
input = sys.stdin.readline
n = int(input())
arr = list(map(int,input().split()))

#LIS사용
arr.reverse()
dp = [1]*n
for i in range(1,n):
    for j in range(0,i):
        if arr[j]<arr[i]:
            dp[i] = max(dp[i],dp[j]+1)


print(n-max(dp))

내림차순 배치를 하는 문제였는데, 리스트를 역으로 정렬해서 오름차순을 이용하는 LIS문제로 바꾸어 풀었다.
그와중에 LIS 틀렸었음 촤하~ㅋ

2. 스티커

코드

import sys
input = sys.stdin.readline
t = int(input())

for _ in range(t):
    n = int(input())
    sticker = [list(map(int,input().rstrip().split())) for i in range(2)]
    
    if n==1:
        print(max(sticker[0][0],sticker[1][0]))
        continue
    
    #dp
    sticker[0][1]+=sticker[1][0]
    sticker[1][1]+=sticker[0][0]
    if n>3:
        for j in range(2,n):
            #교차로 하거나 한칸 건너뛰거나
            sticker[0][j] += max(sticker[1][j-1],sticker[1][j-2])
            sticker[1][j] += max(sticker[0][j-1],sticker[0][j-2])

    print(max(sticker[0][n-1],sticker[1][n-1]))

nct분들이 떠오르는 군여ㅋ
이 문제는 그래도 쉬운 편이었던 것 같다.
n>3조건 안넣으면 틀릴 거 같긴 했는데 도박으로 테스트 돌렸었는데 역시~ 호락호락하지 않았다~

3. 유기농 배추

코드

from collections import deque
import sys

input = sys.stdin.readline

t = int(input())
dx=[-1,1,0,0]
dy=[0,0,-1,1]

def baechu(sx,sy):
    q = deque()
    q.append([sx,sy])
    visited[sx][sy]=True
    
    while q:
        x,y = q.popleft()
        for i in range(len(dx)):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0<=nx<n and 0<=ny<m:
                if graph[nx][ny]==1:
                    if visited[nx][ny]==False:
                        q.append([nx,ny])
                        visited[nx][ny]=True
            
    
for _ in range(t):
    m,n,k = map(int,input().split())
    graph =[[0]*m for i in range(n)]
    visited=[[False]*(m) for i in range(n)]
    #입력받기
    for i in range(k):
        a,b = map(int,input().split())
        graph[b][a]=1
        
    count=0
    for i in range(n):
        for j in range(m):
            if graph[i][j]==1:
                if visited[i][j]==False:
                    baechu(i, j)
                    count+=1
    print(count)

자신감 찾기 위해 푼 문제..ㅎ

요즘 너무 피곤해서 조금만 머리쓰는 문제 나오면 바로 포기하는 거 같다.. 정신차려~~