Coding 공부

# 1149번 RGB 거리

#  RGB 거리엔 N개의 집 1~N 순서대로
# 빨 초 파 중 하나
# 비용의 최소값 구하기
# 1번집의 색 != 2번집의 색
# N번집의 색은 N-1 번집의 색과 같지 않아야한다.

N = int(input())
# RGB
arr = [list(map(int,input().split())) for _ in range(N)]
INF = float('inf')
dp = [[INF] *3  for _ in range(N)]
for i in range(3):
    dp[0][i] = arr[0][i]

for x in range(1,N):
    for y in range(3):
        for z in range(3):
            if y != z:
                dp[x][y] = min(dp[x][y],dp[x-1][z]+arr[x][y])

print(min(dp[N-1]))

처음엔 그냥 dfs를 이용해서 풀어볼려다가, 입력 N이 1000까지라, 3^1000은 시간초과가 날것 같아서 dp로 선회했다.

dp에서 제일 어려운건 동적프로그래밍을 저장할 공간을 설계하는 것 같다. 이 문제를 풀때에 어떻게하면, 이전위치의 저장정보와 최소값 저장할지 고민했었다.

그 해결방법으로 index를 이용했다. dp를 저장하는 y축 index가 동일하지않으면 된다는 점을 착안하여, dp를 설계했다.

# 12865 평범한 배낭



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

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

dp = [0]*(K+1)
for i in range(N):
    weight,value = arr[i]
    for k in range(K,-1,-1):
        if k + weight <= K:
            if k == 0:
                dp[k+weight] = max(dp[k+weight],dp[k]+value)
            else:
                if dp[k]:
                    dp[k+weight] = max(dp[k+weight],dp[k]+value)
print(max(dp))

아마 동적프로그래밍 관련 유명한 문제인걸로 알고 있다.

풀어보고 다른 사람 코드를 보니깐, 2개의 리스트를 만들어서 하나는 최대값이 되는 값을 저장하는 리스트와, 사용여부를 나타내는 리스트를 2개를 두고 하는 경우가 많았다.

그러나 나같은 경우엔 한가지 리스트를 주고, dp의 인덱스값이 0일때는 최대 무게를 넘지 않는한 바로 더해주었고, 그 외에는 해당 인덱스에 저장된 값이 존재하는 경우에만 하도록 했다. 이렇게 했을시에 사용여부를 따로 만들지 않아도 되었다.

여기서 중요했던 점은 역으로 판단을 해줘야했던 것이다. 앞에서부터 순서대로 할시에, 그대로 그 전거가 다음거에 영향을 주기 때문에 끝에서 0으로 가는 것이 중요했다.

import collections
dx=[1,-1,0,0]
dy=[0,0,1,-1]
def bfs(n):
    que=collections.deque()
    que.append(n)
    while que:
        t=que.popleft()
        ax=t//1000000
        ay=t%1000000
        visit[ax][ay]=0
        for i in range(4):
            nx=ax+dx[i]
            ny=ay+dy[i]
            if 0<=nx<M and 0<=ny<N:
                if arr[nx][ny]==1 and visit[nx][ny]==-1:
                    que.append(1000000*nx+ny)
                    visit[nx][ny]=0
    return


T=int(input())

for tc in range(1,T+1):
    N,M,K=list(map(int,input().split()))
    arr=[[0 for j in range(N)] for i in range(M)]
    visit=[[-1]*N for i in range(M)]
    
    for _ in range(K):
        y,x=list(map(int,input().split()))
        arr[x][y]=1
    cnt=0
    for i in range(M):
        for j in range(N):
            if arr[i][j]==1 and visit[i][j]==-1:
                cnt+=1
                bfs(i*1000000+j)
    print(cnt)
    

위의 방식은 BFS를 이용해서 푼 방식이다.

dx=[1,-1,0,0]
dy=[0,0,1,-1]
import sys
sys.setrecursionlimit(10**6)
def dfs(x,y,_cnt):
    dist[x][y]=_cnt

    for k in range(4):
        nx=x+dx[k]
        ny=y+dy[k]
        if 0<=nx<N and 0<=ny<M:
            if arr[nx][ny] and dist[nx][ny]==-1:
                dfs(nx,ny,_cnt)




t=int(input())
for _ in range(t):
    M,N,K=map(int,input().split())
    arr=[[0 for col in range(M)] for row in range(N)]
    dist=[[-1 for col in range(M)] for row in range(N)]
    for _ in range(K):
        y,x=map(int,input().split())
        arr[x][y]=1
    
    cnt=0

    for i in range(N):
        for j in range(M):
            if arr[i][j]==1 and dist[i][j]==-1:
                cnt+=1
                dfs(i,j,cnt)
    print(cnt)

    

DFS를 이용한 방식이다.

BFS나 DFS로 풀면 되는 문제이다. 방문한적이 없고 서로 연결된 것들의 개수를 구하면 되는 문제이다.

T=int(input())

for t in range(T):
    n,m=map(int,input().split(' '))
    k=m-n
    n_result=1
    m_result=1
    k_result=1
    for i in range(1,m+1):
        m_result*=i
    for j in range(1,n+1):
        n_result*=j
    for p in range(1,k+1):
        k_result*=p
    print(int(m_result/(n_result*k_result)))
        

조합을 이용해서 풀면 된다.

import math

def find_num(N):
    x1, y1, r1, x2, y2, r2 = map(int, N.split(' '))
    
    dist = math.sqrt((x1-x2)**2 + (y1-y2)**2)
    
    if(dist == 0):
        if(r1 == r2):
            print('-1')
        else:
            print('0')
    else:        
        if(dist < r1+r2):
            if (dist + min(r1, r2)) == max(r1, r2):
                print(1)
            elif (dist + min(r1, r2) < max(r1, r2)):
                print(0)
            else:
                print(2)
        elif(dist == r1+r2):
            print('1')
        else:
            print('0')

n = int(input())

for i in range(0, n):
    N = input()
    find_num(N)

이 문제는 수학을 이용해서, 각 거리에 따라, 어느위치에 존재하는지 확인해서 출력해주면 된다.

# 5014 스타트링크
# F층 건물 스타트링크 있는 위치 G 강호가있는 층은 S
# U,D
import collections
def bfs(start,end,up,down):
    global F
    visited[start] = 1
    deque = collections.deque()
    deque.append((start,0))
    dx = [up,-down]
    result = 'use the stairs'
    while deque:
        num,cnt = deque.popleft()
        if num == end:
            result = cnt
            break
        for i in range(2):
            nx = num + dx[i]
            if 0 <= nx <= F:
                if not visited[nx]:
                    visited[nx] = 1
                    deque.append((nx,cnt+1))
    return result


F,S,G,U,D = map(int,input().split())
visited = [0]*(F+1)
visited[0] = 1

print(bfs(S,G,U,D))

기본 원리는 BFS를 이용해서, 최단 이동거리를 이용하는거와 같다. 가장 가까이 갈수 있는 경우를 구하는 것이므로 BFS를 썼다.

여기서 주의해야할 점은 F+1 크기만큼의 viisted의 함수를 만들어주고, deque가 전부 비면, 갈수 있는 방안이 없는걸로 판단해야한다.

def check(cnt,total,di):
    global result
    if cnt == arr[0]:
        temp = 1
        for k in di:
            temp *= arr[dire.index(k)+1]/100
        result += temp
        return
    else:
        cu_x,cu_y = total[-1]
        for i in range(4):
            nx = cu_x + dx[i]
            ny = cu_y + dy[i]
            if (nx,ny) not in total:
                check(cnt+1,total+[(nx,ny)],di+[dire[i]])
    


# 동 서 남 북
dx = [0,0,1,-1]
dy = [1,-1,0,0]
dire = ['E','W','S','N']
arr = list(map(int,input().split()))
result = 0
check(0,[(0,0)],[])
print(ccnt)

기본적인 재귀함수를 통해 탐색을 통해 구할 수 있다. 중복이 있으면 재귀를 실행안해주고, 끝까지 갈때까지 해주는 것이다.

이 방법은 되는 것을 구하는 방식인데, 끝까지 가야하므로, 실행시간이 오래걸린다.

def dfs(x,y,persent,cnt):
    global revers_persen,N,total
    if arr[x][y] == 1:
        revers_persen += persent
        return
    if cnt == N:
        return
    arr[x][y] = 1
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if persentlist[i]:
            dfs(nx,ny,persent*persentlist[i],cnt+1)
    arr[x][y] = 0



N,e,w,s,n = map(int,input().split())

e,w,s,n = e/100,w/100,s/100,n/100
dx = [0,0,1,-1]
dy = [1,-1,0,0]
persentlist = [e,w,s,n]
arr = [[0]*29 for _ in range(29)]

revers_persen = 0
dfs(14,14,1,0)
print(f'{1-revers_persen:.10f}')

이 방법은 역으로 되지 않는 경우의 확률을 구해서, 1에서 빼주는 것이다. 이때는, format을 통해 소숫점 자리수까지 나오게 해줘야한다.

def checkheight(alp):
    if alp.isupper():
        return ord(alp) - ord('A')
    else:
        return ord(alp)-ord('a')+26

def custom_minus(a,b,flag):
    if flag:
        return a - b
    else:
        return b - a

def solve(timeslist,flag):
    global N,M,T
    dx = [-1,1,0,0]
    dy = [0,0,1,-1]
    total = 0
    visited = [[True] * M for _ in range(N)]
    x = 0
    y = 0
    timeslist[0][0] = 0
    while total <N*M:
        visited[x][y] = False
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<= nx< N and 0 <= ny <M:
                gap = custom_minus(arr[x][y],arr[nx][ny],flag)
                if abs(gap) <= T:
                    if gap < 0:
                        time_temp = abs(gap)**2
                        
                    else:
                        time_temp = 1
                    timeslist[nx][ny] = min(timeslist[nx][ny],timeslist[x][y]+time_temp)
        next_node_x = -1
        next_node_y = -1
        next_times = INF
        for i in range(N):
            for j in range(M):
                if visited[i][j] and next_times > timeslist[i][j]:
                    next_times = timeslist[i][j]
                    next_node_x = i
                    next_node_y = j
        x = next_node_x
        y = next_node_y
        total += 1
        if next_times == INF:
            break

        



N,M,T,D = map(int,input().split())
arr = [list(map(checkheight,list(input()))) for _ in range(N)]
INF =float('inf')

times = [[INF]*M for _ in range(N)]
reversed_times = [[INF]*M for _ in range(N)]
solve(times,True)
solve(reversed_times,False)
max_height = arr[0][0]

for i in range(N):
    for j in range(M):
        if times[i][j] + reversed_times[i][j] <= D and max_height < arr[i][j]:
            max_height = arr[i][j]
print(max_height)

이 문제는 다익스트라 알고리즘을 이용해서 푼 문제이다.

ord라는 함수를 통해, 알파벳을 문제에 주어진 숫자로 변경시켜주었다.

이 문제는 처음에 냈을때 틀렸는데, 그 이유는, 문제를 제대로 읽지 않고, 해당 목적지까지 정해진 시간 D 까지만 가면 되는 줄 알았는데, 처음 호텔위치로 돌아와야했다.

이 문제는 단순히 다익스트라를 두번 돌리면 된다.

출발지와 목적지까지 올라가는 다익스트라 한번

목적지에서 출발지로 돌아오는 다익스트라 한번

하면된다.

이 문제를 두개의 함수로 나뉘어서 하기 싫어서 flag라는 변경점을 주고, 하산할때에는 뺄셈 방식을 반대로 해주게 하여, 하나의 다익스트라를 찾는 함수로 올라갈때와 내려갈때를 구현했다.

그리고 문제를 풀고난뒤, 다른사람들 풀이를 보니, 전체 N이 작아서 플로이드 와샬 방법으로 풀어도 된다고 한다.

하지만, 플로이드 와샬이 아직 잘 몰라서 그 방법으로 못 풀어봤다.

나중에 기회가 되면 플로이드 와샬로도 풀어볼 예정이다.