안될 가능성이 높으나 15기 소프트웨어 마에스트로에 지원했습니다. 뭐든 도전해보는게 중요하니까요.

따라서 하던 DP 잠시 미뤄두고 소마 기출 푸는거에 집중하려 합니다. 기출에 DP도 포함되어 있으니 겸사겸사 공부하겠습니다.

1012 - 유기농 배추

BFS로 1이 뭉쳐있는 구역 갯수를 파악하는 문제입니다.

T = int(input())
que = deque([])
ans = []

테스트케잇,큐,답을 출력할 ans를 선언하겠습니다.

for _ in range(T):
    
    M,N,K = map(int,input().split())
    graph = [[0]*M for _ in range(N)]
    visited = [[0]*M for _ in range(N)]

테스트케이스만큼 루프를 돌려주고, 가로,세로,배추가 심어져 잇는 위치를 받아서

    for _ in range(K):
        a,b = map(int,input().split()) 
        graph[b][a] = 1

그래프에 표기해줍니다. 주의할 점은 이곳 그래프의 표기 방식은 열과 행이 반대라서 a와 b를 거꾸로 입력받아야 정상적으로 출력됩니다.

    
    cnt = 0
    for i in range(N):
        for j in range(M):
            if not visited[i][j] and graph[i][j] == 1:
                bfs(i,j)
                cnt += 1

다음으로 cnt변수를 선언하고 그래프를 순회하는 동안 방문하지 않은 지역이고 해당 지역이 1이라면 BFS 탐색으로 돌아줍니다. 탐색 후에는 cnt변수를 1 올려줍니다.

    ans.append(cnt)

for values in ans:
    print(values)

cnt변수를 ans에 추가하고 values로써 출력하면 답이 출력됩니다.

from collections import deque
dx = [-1,1,0,0]
dy = [0,0,1,-1]

BFS는 항상 먹던 그 맛입니다. dx,dy로 상하좌우 탐색 설정하고

def bfs(x,y):
    que.append([x,y])
    visited[x][y] = 1

탐색에 들어왔으면 해당 위치는 방문여부 O로 표기 해줍니다.

    while que:
        x,y = que.popleft()
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y
            if nx<0 or ny<0 or nx>=N or ny>=M:
                continue

4방향 탐색을 실시하는동안 그래프 밖을 벗어나려하면 continue로 막아주고

            if not visited[nx][ny] and graph[nx][ny] == 1:
                visited[nx][ny] = 1
                que.append([nx,ny])

만약에 탐색하다가 방문을 안했고 해당 지역이 1이라면 탐색 후보지에 넣어주고 방문여부 O로 표기해주면 됩니다.

---

9461번 - 파도반 수열

그림과 같은 삼각형이 나선 모양으로 놓여저있고 P(N)은 N번째 삼각형 변의 길이라 할때, P(N)을 구하시오.

라는 DP문제입니다.

---

분석

먼저 저는 P(4)에서 점화식을 도출하려고 봤더니
P(4) = P(3)+P(1) 그리고 P(4) = P(3)+P(2) 라는 식이 두개가 도출되어 점화식을 세우는게 힘들었습니다.

그래서 확실히 구분되는 지점을 봤더니 P(11)을 살펴보면 P(11) = P(10) + P(6)인데 P(10)과 P(6)은 각각 9와 3인 수열에 하나밖에 없는 고유 수라 P(11)의 연산이 가능한 경우는 저것밖에 없었습니다.

따라서 본 문제에서 P(n)은 P(n-1)+P(n-5)라는 점화식 도출이 가능합니다.

---

코딩

T = int(input())
for _ in range(T):
    n = int(input())
    print(dp(n-1))

먼저 테스트케이스를 받고 받은만큼 dp함수를 재귀로써 돌려줍니다.
n-1로 변수에 넣은 이유는 문제는 P(1)부터 시작하지만 저는 P(0)부터 시작하기 때문입니다.

memo = [0]*101
def dp(N):
    if N == 0 : return 1
    if N == 1 : return 1
    if N == 2 : return 1
    if N == 3 : return 2
    if N == 4 : return 2

메모이제이션을 하나 만들어주고 0,1,2 첫 세 삼각형은 1로 초기화, 3,4 두개의 삼각형은 3,4로 초기화를 진행해줍니다. 3,4를 굳이 넣어주는 이유는 예를 들어 초기화 식 없이 점화식 P(4)를 작동하게 되면 P(3) + P(-1)이라는 음수를 불러오는 사태가 발생하므로 이를 방지하기 위함입니다.

    if memo[N]:
        return memo[N]
    memo[N] = dp(N-1) + dp(N-5)
    return memo[N]

메모이제이션에 있으면 해당 값으로 return 하고 아니라면 현재 탐색중인 N값을 메모이제이션에 넣고 해당 값으로 return 하면 됩니다.

---

---