Coding 공부

import sys
input = sys.stdin.readline
def dfs(node):
    global result 
    if not len(graph[node]):
        ball_cnt_list[parent_list[node]] += (ball_cnt_list[node] -1)
        result += abs(ball_cnt_list[node] - 1)
    else:
        for next_node in graph[node]:
            dfs(next_node) 
        if parent_list[node] != -1:
            ball_cnt_list[parent_list[node]] += ball_cnt_list[node] - 1
            result += abs(ball_cnt_list[node] - 1)



while True:
    N = int(input())

    if N == 0:
        break
    graph = [[] for _ in range(N+1)]
    parent_list = [-1 for _ in range(N+1)]
    ball_cnt_list = [0 for _ in range(N+1)]
    indegree = [0 for _ in range(N+1)]
    for _ in range(N):
        node_num,ball_cnt,*arg = map(int,input().split())
        if arg[0]>0:
            for child_node in arg[1:]:
                graph[node_num].append(child_node)
                parent_list[child_node] = node_num
                indegree[child_node] += 1
        ball_cnt_list[node_num] = ball_cnt

    result = 0
    for k in range(1,N+1):
        if indegree[k] == 0:
            dfs(k)
    print(result)

 이 문제를 해결하는데 어려움을 겪었다.

이 문제를 해결하는 방식은 가장 끝 리프노드부터 1씩 무조건 맞춰주는 것이다.

그리고 그때의 절대값들을 전부 더해주는 방식을 해주면 된다.

현재 노드에서 1와의 차이를 부모노드로 옮겨주고,

그때 차이의 절대값을 결과에 계속 더해주면 된다.

# dotorya님 풀이

import sys
input = sys.stdin.readline
def dfs(node):
    global result 
    cnt = ball_cnt_list[node] -1

    for next_node in graph[node]:
        cnt += dfs(next_node)

    result += abs(cnt)
    return cnt



while True:
    N = int(input())

    if N == 0:
        break
    graph = [[] for _ in range(N+1)]
    ball_cnt_list = [0 for _ in range(N+1)]
    indegree = [0 for _ in range(N+1)]
    for _ in range(N):
        node_num,ball_cnt,*arg = map(int,input().split())
        if arg[0]>0:
            for child_node in arg[1:]:
                graph[node_num].append(child_node)
                indegree[child_node] += 1
        ball_cnt_list[node_num] = ball_cnt

    result = 0
    for k in range(1,N+1):
        if indegree[k] == 0:
            dfs(k)
    print(result)

두 번째 풀이는 dotorya님 풀이를 복기한 것이다.

끝노드부터 하는 것은 동일하다.

그리고 현재의 격차를 상위노드로 전달해주고, 결과에는 그 절대값을 계속 누적해서 더해주면 되는 것이다.

from collections import deque
def func(x):
    return x[0]
T = int(input())

for _ in range(T):
    N,M = map(int,input().split())

    arr = list(map(int,input().split()))
    queue = deque()
    for ind,val in enumerate(arr):
        queue.append((val,ind))

    cnt = 0
    while queue:
        val, ind = queue.popleft()
        if not queue or val >= max(queue,key=func)[0]:
            cnt += 1
            if ind == M:
                break
        else:
            queue.append((val,ind))

    print(cnt)

문제에 주어진대로 구현을 하면 되는 문제이다.

단 다른점은 queue에 초기에 현재의 값과 idx의 값을 동시에 넣어주고,

원하는 ind에 도착하면 멈춰주는식으로 했다.

import sys

input = sys.stdin.readline

def dfs(state,order_cnt):
    global result
    if order_cnt >= P:
        result = min(result,dp[state])
        return
    else:
        if dp[state] > result:
            return

        else:
            for cu_node in range(N):
                if state & 1<<cu_node:
                    for next_node in range(N):
                        if not state & 1<<next_node and dp[state|1<<next_node] > dp[state] + arr[cu_node][next_node]:
                            dp[state|1<<next_node] = dp[state] + arr[cu_node][next_node]
                            dfs(state|1<<next_node,order_cnt+1)



N = int(input())


arr = [list(map(int,input().split())) for _ in range(N)]


state_string = input()
state = 0
P = int(input())
order_cnt = 0
stack = []
result = float('inf')
for i in range(N):
    if state_string[i] == 'Y':
        state += 1<<i
        order_cnt += 1
        stack.append(i)
dp = [float('inf') for _ in range(2**N+1)]
dp[state] = 0
if order_cnt == P:
    print(0)
else:
    dfs(state,order_cnt)
    if result == float('inf'):
        print(-1)
    else:
        print(result)

재귀를 이용해서 문제를 풀었다.

먼저 비트로 각 발전소의 상태를 구분해주었다.

발전소의 위치와 비트의 위치를 동일시해서, 0번째 비트가 1이면, 0번 발전소가 켜져있는것이다.

그러므로 우리는 마지막으로 들어온 입력을 이용해 현재 발전소의 상태를 비트로 표현을 해준다.

그리고 dp라는 테이블에 발전소를 고치는 최소값을 갱신해주기 위해, 만들어두었다.

그 크기는 state의 크기이므로 2**N까지가 필요하다. 

미리 만들어놓은 상태에서 dfs 함수를 통해 재귀를 하면서 문제를 푸는데 접근을 했다.

2중 포문을 돌면서 dfs에 들어온 state를 통해, 현재 켜져있는 발전소를 구분을 해준다.

그리고 발전소가 켜져있으면 두번째 for문을 통해, 켜지지 않은 발전소를 구하고, 현재 state에서 발전소를 켰을때 비용이 더 작은 경우에

추가적으로 dfs를 하는 작업을 해주었다.

그리고 문제에 주어진 P보다 크거나 같으면 종료되도록 함수를 짰다.

import sys

input = sys.stdin.readline

def dfs(state,order_cnt):
    if dp[state] != -1:
        return dp[state]
    if order_cnt >= P:
        dp[state] = 0
        return 0
    else:
        min_value = float('inf')
        for cu_node in range(N):
            if state & 1<<cu_node:
                for next_node in range(N):
                    if not state & 1<<next_node:
                        min_value = min(min_value,dfs(state|1<<next_node,order_cnt+1) + arr[cu_node][next_node])
        dp[state] = min_value
        return dp[state]

N = int(input())


arr = [list(map(int,input().split())) for _ in range(N)]


state_string = input()
state = 0
P = int(input())
order_cnt = 0
for i in range(N):
    if state_string[i] == 'Y':
        state += 1<<i
        order_cnt += 1
dp = [-1 for _ in range(2**N+1)]
if order_cnt >= P:
    print(0)
elif order_cnt == 0:
    if P:
        print(-1)
    else:
        print(0)
else:
    result = dfs(state,order_cnt)
    if result == float('inf'):
        print(-1)
    else:
        print(result)

좀 더 깔끔한 풀이는 다음과 같다.

return 되는 값을 이용해 바로 출력이 가능하게 하는것이다.

기본 적인 원리는 같으며, 반환되는 값을 비교를 해서 최저값을 갱신을 해주는 것이다.

그리고 조건을 만족했을때에는 0을리턴하는식으로 해주는 것이다.

이 풀이가 dp라는 테이블을 좀더 생산적으로 쓰면서 풀 수 있는 방식이다.

import sys

def check(idx,cnt):
    global result
    if idx == N:
        result = max(result,cnt)
        print(result)
        exit()
        return
    else:
        for next_idx in range(idx+1,N,2):
            if dp[idx][next_idx]:
                check(next_idx+1,cnt+1)
input = sys.stdin.readline

N = int(input())

arr = list(map(int,input().split()))

dp = [[ True  if i == j else False for j in range (N)]  for i in range(N)]
for i in range(N-1):
    if arr[i] == arr[i+1]:
        dp[i][i+1] = True

for i in range(2,N):
    for j in range(N-i):
        if arr[j] == arr[j+i] and dp[j+1][j+i-1]:
            dp[j][j+i] = True

max_num = N//2
result = -1
check(0,0)
print(result)

이 문제는 boj.kr/10942에서 풀었던 전체 배열에 대한 팰린드롬의 dp를 구해놓은 상태로 풀었다.

먼저 전체 배열의 대한 팰린드롬 상태를 dp에 저장시켜놓는다.

그리고 우리는 check를 해주면 된다.

우리는 짝수개 만큼 나눌수 있다.

그러면 우리는 현재 위치에서 짝수번째 떨어진 위치의 dp 상태값을 통해 팰린드롬이면 재귀를 통해

N번째 index에 도착할때까지 계속해준다.

그리고 최초로 도착을 했을때가 가장 최대 짝수팰린드롬이므로, 그때 값을 출력해주면 된다.

왜냐하면, 우리는 2칸단위부터 자르기 때문에,

가장 먼저 도착하는 것이, 가장 많이 자른것이기 때문이다.

이 문제는 이렇게 dp로 푸는 방식말고도 그리디방식으로도 푸는 방식이 있다하지만, 배움이 부족해,

그 풀이는 정확히 이해하지 못했다.

import heapq
import sys

input = sys.stdin.readline
N,M = map(int,input().split())


graph = [{} for _ in range(N+1)]
total_pay = 0
for _ in range(M):
    x,y,pay = map(int,input().split())
    graph[x][y] = pay
    graph[y][x] = pay
    total_pay += pay

INF = float('inf')

distance = [INF for _ in range(N+1)]
visited = [False for _ in range(N+1)]
node_list = []
heapq.heappush(node_list,(0,1))
result = 0
distance[1] = 0
cnt = 0
while node_list:
    dis,node = heapq.heappop(node_list)

    if visited[node]:
        continue
    result += dis
    cnt += 1
    visited[node] = True
    for next_node in graph[node]:
        if distance[next_node] > graph[node][next_node]:
            distance[next_node] = graph[node][next_node]
            heapq.heappush(node_list,(distance[next_node],next_node))


if cnt == N:
    print(total_pay-result)
else:
    print(-1)

이 문제는 전형적인 MST 문제였다.

그래서 나는 MST에서 익숙한 프림알고리즘을 이용해, 돌렸으며, 방문한 전체 노드의 수를 세주었다.

만약 전체 노드의 개수가 일치 하지 않으면, 모든 노드들을 연결 할 수 없으므로, -1을 출력해주었고,

전체 노드의 개수가 같으면, 원래 전체 비용에서 MST했을때의 비용을 빼주어서, 절약한 값을 출력해주었다.

import sys
from collections import deque
input = sys.stdin.readline


def bfs(point,dis_list,flag):
    dis_list[point[0]][point[1]] = arr[point[0]][point[1]]
    dx = [-1,0]
    dy = [0,1]

    stack = deque()
    stack.append((point[0],point[1]))

    while stack:
        x,y = stack.popleft()

        for i in range(2):
            nx = x + dx[i]
            ny = y + dy[i]*flag
            if 0<=nx<N and 0<=ny<M:
                if dis_list[nx][ny] < dis_list[x][y] + arr[nx][ny]:
                    dis_list[nx][ny] = dis_list[x][y] + arr[nx][ny]
                    stack.append((nx,ny))
        


N,M = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(N)]
INF =float('inf')
start_distance = [[-INF for _ in range(M)] for _ in range(N)]
end_distance = [[-INF for _ in range(M)] for _ in range(N)]

start_point = (N-1,0)
end_point = (N-1,M-1)
bfs(start_point,start_distance,1)
bfs(end_point,end_distance,-1)

max_value = -INF

for i in range(N):
    for j in range(M):
        if start_distance[i][j] + end_distance[i][j] > max_value:
            max_value = start_distance[i][j] + end_distance[i][j]
print(max_value)

 이 문제는 저는 BFS를 이용해서 풀었다.(근데 아직 푼사람이 적은지 solved.ac 기준에는 다이나믹 프로그래밍 밖에 없다.)

boj.kr/2206 문제와 비슷한 방식으로 풀었다.

이 문제를 봐보면 상승이나 하강은 특정한 방향으로 밖에 가지 못한다.

이 점을 이용해서 우리는 특정지점 (x,y)까지의 최대값을 bfs를 이용해 갱신할 수 잇을것이다.

그래서 나는 (N-1,0)에서 상승을 시작하므로, 이 지점을 시작으로 갈수 있는 모든지점에 대해, bfs를 돌려 최대값을 갱신을 해주었다.

똑같은 방식으로 (N-1,M-1) 위치로 하강을 해야하므로, 이 위치에서 하강의 반대방향으로 BFS를 돌리면서 최대값을 갱신을 해주었다.

그러면 우리는 상승을 할때의 각 지점의 최대값 하강을 할때의 각 지점의 최대값을 가지고 있는 행렬을 가지게 되었다.

이 두 행렬의 합을 전체 탐색을 하면서, 가장 큰 값을 출력해주면 되는 문제이다.

import sys
from collections import deque
input = sys.stdin.readline
N,M = map(int,input().split())

arr = []
aircon = deque()
visited = [[[True for _ in range(4)] for _ in range(M)] for _ in range(N)]
total_set = set()
for x in range(N):
    temp = list(map(int,input().split()))
    for y in range(M):
        if temp[y] == 9:
            aircon.append((x,y,[0,1,2,3]))
            temp[y] = 0
            total_set.add((x,y))
            for i in range(4):
                visited[x][y][i] = False

    arr.append(temp)


if aircon:
    dx = [-1,0,1,0]
    dy = [0,-1,0,1]
    rotate_dict = {
        1 : [0,-1,2,-1],
        2 : [-1,1,-1,3],
        3 : [3,2,1,0],
        4 : [1,0,3,2]
    }
    # 북,서,남,동
    while aircon:
        x,y,dire = aircon.pop()
        for i in dire:
            nx = x + dx[i]
            ny = y + dy[i]
            while 0<=nx<N and 0<=ny<M and visited[nx][ny][i] and visited[nx][ny][(i+2)%4] and not arr[nx][ny]:
                visited[nx][ny][i] = False
                visited[nx][ny][(i+2)%4] = False
                total_set.add((nx,ny))
                nx = nx + dx[i]
                ny = ny + dy[i]
            if 0<=nx<N and 0<=ny<M and arr[nx][ny]:
                if rotate_dict[arr[nx][ny]][i] != -1:
                    visited[nx][ny][i] = False
                    visited[nx][ny][(i+2)%4] = False
                    visited[nx][ny][rotate_dict[arr[nx][ny]][i]] = False
                    total_set.add((nx,ny))
                    aircon.append((nx,ny,[rotate_dict[arr[nx][ny]][i]]))
                else:
                    visited[nx][ny][i] = False
                    visited[nx][ny][(i+2)%4] = False
                    total_set.add((nx,ny))
    print(len(total_set))
else:
    print(0)

tony9402님이 1회차 문제들 중에 푸는데 가장 오래걸렸던 문제였다.

처음에 아슬아슬하게 통과했는데, 이 코드 같은경우엔 통과가 될수도 안될수도 있을정도의 커트라인에 걸친 코드이다.

이 첫 풀이의 아이디어는 다음과 같다. N*M*4의 visitied를 만들어놔서, 방문표시를 해주었다.

그리고 방문표시를 할때, 서로 반대되는 경우와 회전을 했을때에는, 반대되는 경우 + 회전하는경우까지 전부 방문 처리를 해주었다.

위와 같은 작업을 하고, BFS를 돌리면서 전체 방문을 한 위치들을 set에 넣어서 길이를 출력해주었다.

import sys
from collections import deque
input = sys.stdin.readline
N,M = map(int,input().split())
def func(row):
    return row.count(True)
arr = []
aircon = deque()
visited = [[False for _ in range(M)] for _ in range(N)]
for x in range(N):
    temp = list(map(int,input().split()))
    for y in range(M):
        if temp[y] == 9:
            aircon.append((x,y,[0,1,2,3]))
            visited[x][y] = True

    arr.append(temp)


if aircon:
    dx = [-1,0,1,0]
    dy = [0,-1,0,1]
    rotate_dict = {
        1 : [0,-1,2,-1],
        2 : [-1,1,-1,3],
        3 : [3,2,1,0],
        4 : [1,0,3,2]
    }
    # 북,서,남,동
    while aircon:
        x,y,dire = aircon.pop()
        for i in dire:
            nx = x + dx[i]
            ny = y + dy[i]
            while 0<=nx<N and 0<=ny<M :
                if arr[nx][ny] == 9:
                    break
                visited[nx][ny] = True
                if 0<=nx<N and 0<=ny<M and arr[nx][ny]:
                    if rotate_dict[arr[nx][ny]][i] != -1:
                        i = rotate_dict[arr[nx][ny]][i]
                    else:
                        break
                nx = nx + dx[i]
                ny = ny + dy[i]

    b = sum(list(map(func,visited)))
    print(b)
else:
    print(0)

 깔끔한 풀이는 다음과 같다.

이 풀이는 다음과 같다. 에어컨 바람은 언제 멈추면될것인가 이다.

문제를 읽어보면 에어컨 바람이 멈출 만한 곳은 총 3가지 경우이다.

1. 연구실 범위를 벗어났을때

 - 당연하게 연구실 밖으로 바람이 벗어나면 돌아올 방법이 없으므로, 연구실 범위가 벗어났을때, 에어컨 바람은 그만둔다.

2. 다른 에어컨을 만났을때

 - 다른 에어컨을 만났을때 왜 멈춰야하는지 의문을 표할수도 있다. 하지만 생각을 해보면, 우리는 어떠한 경로를 통해 

   A에어컨에서 B에어컨까지 왔다. 그러면 B에어컨에서도 똑같이 A에어컨으로 갈 수 있는 경로가 생긴 것이다.

  각 에어컨은 상하좌우로 전부 돌기 때문에, 가능한 것이다. 그러므로 다른 에어컨에 만났을 때, 거기서부터의 바람의 이동은 그 에어컨에서 다시 탐색을 하면 되는 것이다.

3. 물건1,2의 방향과 수직되는 방향의 바람이 들어왔을 때

 - 이때는 경우2번을 생각해보면 똑같다. 우리는 특정한 경로를 통해 물건1, 2로 왔을 것이다. 그런데 수직되는 방향으로 바람이 들어오면, 그 바람은 반대로 되돌아 간다. 즉, 우리가 왔던 길로 되돌아가서, 우리가 최초로 바람이 왔던 에어컨으로 돌아간다.

  그러면, 그때의 반대방향으로 가는 바람은 우리가 상하좌우를 전부 탐색을 할 것이기때문에, 이미 탐색범위에 있다.

 그렇기 때문에 굳이 다시 탐색을 할 필요가 없다.

그러므로 위의 3가지경우를 제외하고는 방향을 계속 전환을 해주면서 방문표시를 해주면된다.

이 방문 표시는 재방문을 방지하기 위한 방문표시가 아니라, 에어컨의 바람이 어디까지 영향을 줬는지 세기 위한 것이다.

그래서 나는 3가지 경우를 제외하고는 계속해서 돌도록 while문을 돌려주었고,

전부 돌리고 난뒤에 visited의 True의 개수를 세어, 출력을 해주었다.

낮은 난이도의 문제였지만, 처음 잘못잡은 아이디어와 접근방법으로 인해 가장 오래걸리고 고생했던 문제였다. 

N,X = map(int,input().split())

arr = list(map(int,input().split()))

if max(arr) == 0:
    print('SAD')
else:
    value = sum(arr[:X])

    max_value = value
    max_cnt = 1

    for i in range(X,N):
        value += arr[i]
        value -= arr[i-X]
        if value > max_value:
            max_value = value
            max_cnt = 1
        elif value == max_value:
            max_cnt += 1

    print(max_value)
    print(max_cnt)        


        

범위 내의 최대 누적자수를 구하면 되는 문제이다.

그래서 나는 슬라이딩 윈도우를 이용해 X의 크기만큼의 첫 방문자수를 구한뒤 한칸씩 이동하면서 더해주고 빼주는 작업을 반복했다.

그리고 값이 갱신되면 1로 초기화를 해주고, 그렇지 않고 최대값과 같은 값이 나왔을때는 더해주는 방식으로 풀 수 있었다.