Dalin's Archive

문제로 가기 접근 🌰🍂 DP로 풀었다. 어떤 색으로 집을 칠할지, 몇 번째 집인지를 담은 2차원 리스트를 만들었다. 1번 집은 그냥 칠하면 된다. 그 이후 집들은 그 이전 집 색깔과 겹치지 않게 최소 비용으로 칠했다. 예를 들어, 현재 집을 빨강으로 칠할 때의 최소 비용을 구해야 하는 경우를 생각해보자. 그 이전 집이 초록일 때, 파랑일 때 최소 비용 중 싼 것을 택하고, 현재 집을 빨강으로 칠하는 비용을 더해서 dp 테이블을 채웠다. 코드 👩‍💻 import sys input = sys.stdin.readline N = int(input()) house_color_costs = list(list(map(int, input().split())) for _ in range(N)) dp = [[0] * 3 ..

문제 보러가기 접근 🍁 쭉~ 입력을 받은 후에 정렬을 했다. 정렬을 하는 게 매우 중요하다..!! start와 end는, 다른 선들과 겹치지 않는 선은 계산을 끝내고, (다른 선들과 겹칠 가능성을 가진) 당시에 가장 긴 선을 의미한다. 맨 처음 시작점, 도착점을 각각 start, end에 대입했다. 그 다음부터 각각의 시작점, 도착점과 start, end를 비교해 보면 아래 그림의 세 가지 경우 중 하나가 된다. (정렬을 했으니까 항상 그 시점의 시작점보다 start가 작거나 같을 것이다. 그래서 아래 세 가지 경우만 있다.) 1) 두 선이 겹치고, 그 때 꺼낸 도착점이 end보다 뒤에 있는 경우. 그러면 start는 그대로 두고, end는 그때 꺼낸 도착점으로 업데이트한다. 2) 두 선이 겹치고, 그 ..

문제 보러 가기! 문제를 꼼꼼히 읽고 구현하려고 했다~ 큐를 하나 만들어서 은행 대기 줄을 구현했다. 이미 줄 서있는 사람들은 이 큐에 넣고 시작했고, 나중에 오는 사람들은 시간이 될 때 큐 안에 넣었다. 1. 큐의 맨 앞에 있는 고객을 만나기 2. 고객 업무 처리하기 1) 고객에게 필요한 시간이 T보다 크거나 같으면 T초 동안 그 고객을 만났다. 시간을 1초씩 움직이면서, 그 고객 아이디를 출력했고, 만약에 그때 은행에 들어온 고객이 있는지 체크하고 있으면 큐 안에 넣어주었다. => 다 끝난 후에, 고객이 다시 뒤에 가서 서야 하면(필요한 시간이 T보다 컸으면) 큐의 맨 뒤에 넣었다. 2) 고객에게 필요한 시간이 그보다 작으면 필요한 시간만큼만 고객을 만나면 된다. 이때도 시간을 1초씩 움직이면서, 그..

문제로 가기 문제 소개, 아이디어 정훈이 -> 상대방의 순서로 카드를 윗장부터 하나씩 분배하고 있다. 카드 합이 더 큰 사람이 이긴다. 밑장 빼기를 최대 1번 해서, 정훈이가 얻을 수 있는 최대 카드 합을 구하는 문제이다. 밑장 빼기 최대 1번이니까 할 수도 있고, 안 할 수도 있는 것이다. 일단 안할 때 정훈이가 얻는 카드 합을 구했다. 그걸 ans에 대입했다. 그리고 밑장을 뺄 경우를 따져보면서, 각각의 상황에서 정훈이가 얻는 카드 합을 ans과 비교해서, 클 때의 값을 ans에 넣었다. 그러면 밑장 뺄 때 정훈이가 가진 카드의 합이 어떻게 되는지는 어떻게 구했을까? 일단 그림을 그려봤다 ! 정훈이 차례에 밑장을 빼면, 그 때를 포함해서 이후의 원래 상대가 가질 예정이었던 카드의 합과 정훈이가 가질 ..

와아아~~~ 이 문제를 풀어서 편안하게 잠잘 수 있겠다 ㅎㅎ 처음에는 메모리 초과 해결하느라고, 나중에는 게임 종료 후 빈 문자열이면 EMPTY 출력하는 걸 깜박해서 많이 틀렸다.. 문제 보러 가기 아이디어 카드의 갯수, 사람의 수가 최대 9..!! 사람들이 어떤 순서로 카드를 낼 수 있는지를 순열로 구했다. 각 순열대로 했을 때의 결과를 리스트로 저장했고, 사전순으로 출력이니까 정렬을 한 후에 출력했다. 같은 결과가 나오면 하나로 출력하라고 해서, set을 이용했다. (set에 저장한 후에 마지막에 리스트로 바꿔서 정렬했다.) 처음에는 모든 경우의 순열을 다 구했다. 그랬더니 메모리 초과가 나왔다..!! -예) 1번 사람이 카드 한 장, 2번 사람이 카드 한 장을 가진 경우라고 생각해보자. 사람들이 어..

[문제 보러 가기!](https://www.acmicpc.net/problem/17265 DFS로 풀었다. DFS에서 좌표, 그때까지 계산한 값, 연산자(그 직전이 연산자인 경우만)를 들고 다닌다. 학교에 도착하면(i==N-1 and j==N-1), 가능하다면 정답을 업데이트해준다. 아래, 오른쪽으로만 가라고 했으니까 그렇게 진행한다. 숫자일 때는 그 전의 연산자를 활용해서 계산해줬고, 연산자일 때는 숫자는 그대로 두고 그 연산자를 가지고 다음으로 넘겨주었다. 한 번 틀렸습니다.를 만났는데, 그 이유는 max_answer을 -1로 세팅하고 시작했기 때문이었다.. 처음에 0을 만나고 계속 -, 5, -, 5, -, 5, ... 이런 식으로 진행될 수도 있으니까 -1로 세팅하면 안되는 것이었다. 최대값을 구..

문제로 가기! 헐 ㅠㅠㅠㅠ 내가 이 문제를 풀다니ㅠㅠㅠ 나는 DP 문제는 식 생각하는 게 어려워서 좀 자신이 없다... 그래서 이 문제를 봤을 때도 '내가 풀 수 있을까?'하면서 봤다. 그래도 나름 종이에 끄적끄적하다보니 이런 식으로 DP 풀면 되겠다는 생각이 났다. 그리고 하나 하나 구현했더니 맞았습니다 !! 가 나왔다 ㅠㅠㅠ 코드를 쓰기 전에 미리 생각하는 게 중요한 것을 다시 한번 느꼈다 ! 접근 일단 천사 다리부터 시작하는 경우, 악마 다리부터 시작하는 경우를 나눠서 생각했다. 악마 다리에서 시작하는 예시를 가지고 설명하겠다. 일단 dp 테이블을 다 0으로 세팅하고 시작한다. dp 테이블은 3차원 리스트로 만들었다. 무슨 다리인지, 각 다리에서 몇 번째 돌인지, 마법 두루마리에서 몇번째 글자인지를..

문제로 가기 싸피에서 prim 알고리즘을 배웠다.! 관련된 문제를 풀고 싶어서 푼 문제! Prim에서 조금 응용해야 한다. 여기에서는 남초 대학, 여초 대학을 번갈아서 연결하는 조건까지 추가되었다! 힙에 넣을 때, 이전 노드의 타입(여초인지 남초인지) & 현재 노드의 타입까지 추가해서 풀었다 ! import heapq import sys input = sys.stdin.readline N, M = map(int, input().split()) university_type = [0] + input().split() visited = [False] * (N + 1) distance = [9999999999] * (N + 1) adj = [[] for _ in range(N + 1)] for _ in rang..

문제 보러 가기! N개의 집(정점)이 주어지고, 집과 집을 연결하는 도로(간선)가 주어진다. 도로는 단방향 간선이고, 이동하는 데 걸리는 시간이 주어진다. 도로는 모든 집들 간의 이동이 가능하게 했다. 모든 집에서 생일을 맞은 인수의 집으로 오고 가는데, 이때 오가는 시간이 가장 오래 걸리는 집이 얼마나 걸리는지 구하는 문제이다. 그러면 인수네 집 -> 다른 모든 집으로 가는 데 드는 최소 시간도, 다른 모든 집 각각에서 인수네 집으로 가는 데 드는 최소 시간도 모두 알아야 한다. 인수네 집에서 다른 모든 집들 가는 최단 경로는 다익스트라로 할 수 있다는 건 처음부터 알았다. 다른 각각의 집에서 인수네 집으로 가는 최단 경로는 어떻게 구할까.. 그게 고민이었다. 처음에는 마음 편하게 ! 모든 정점 간의 ..

플로이드-워샬 알고리즘으로 풀었는데 처음에는 답이 안나왔다. 주의! 아래 코드는 정답 아님. import sys input = sys.stdin.readline def FW(): for k in range(1, N + 1): # 경유지 for i in range(1, N + 1): for j in range(1, N + 1): distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j]) INF = 100 * 100000 + 1 N = int(input()) M = int(input()) distance = [[INF] * (N + 1) for _ in range(N + 1)] # 초기화(자기 자신으로 갈 때 0) for i in range(..