Dalin's Archive

문제 보러 가기! 모든 지점에서 모든 지점까지 가는 최소 비용(최단 경로)을 구해야 하므로 플로이드 와샬 알고리즘을 썼다. 일반적인 플로이드 와샬과 다르게, 최소 비용 자체가 정답이 아니라, 최소 비용이 되기 위해서는 어디를 가장 먼저 방문해야 할지를 구하는 문제였다. 그래서 이동할 때 드는 최소 비용을 저장한 2차원 리스트에 더해서, 최소 비용이 되려면 어디를 가장 먼저 방문해야 하는지 저장하는 2차원 리스트(move)도 만들었다. 그리고 플로이드 와샬 알고리즘을 사용하면서, i 에서 j 지점으로 가는데 k를 들러서 가는 게 최소 비용이라면 ! 비용을 갱신하면서, 가장 먼저 방문할 지점도 업데이트해줬다. 틀렸던 이유 양방향인데 단방향으로 생각해서 ㅠ 자기 자신으로 갈 때 처음 방문할 지점을 '-..

문제 보러 가기! DP문제 !! 입력이 특이한 것 같다..- 여러 줄에 걸쳐서 N개의 정수가 주어지는 부분, 테스트케이스가 몇 개인지 안 알려주고 맨 끝에 0이 오는 부분. try, except를 이용해서 편하게 테스트케이스 수만큼 동작하게 했다. 여러 줄에 걸쳐서 N개 정수가 주어지는 부분을 위해서, 리스트로 받고 개수를 세다가 N개가 되면 그만 받게 했다. dp table을 2차원으로 만들었다. 세로: 몇 번째 이동한 것인지 가로: 해당 위치 값: 최대로 얻는 수익!! (예- 1번째로 이동해서 1번째 칸에 도달했을 때 얻는 최대 수익) 세로 첫 줄은 채우고 시작한다. (1~S만큼 이동할 수 있으니까 그만큼만 채우기) 그 다음 세로 줄들을 돌면서, 가로를 채운다. 이런 식으로 된다..! 그 가로까지 올..

문제 보러 가기! 처음 풀이- 시간 초과 🎇 가방 많이 넣을 수 있는 것부터 하나씩 보면서, 보석을 가격 비싼 순(가격 같으면 무거운 순)으로 봤다. 그 가방에 보석을 넣을 수 있으면, 보석 없애고 가방도 없애고.. 그 가격을 정답에 더했다. 그 가방에 그 보석을 못 넣으면 그냥 보석을 없앴다. (어차피 이후 가방에도 그 보석이 무거워서 못 넣으니까) 예제는 맞기는 한데,, 그랬더니 시간 초과 ㅠ 코드는 이랬다. import sys, heapq input= sys.stdin.readline N,K = map(int,input().split()) jewelries = [] backpacks = [] for _ in range(N): m, v = map(int,input().split()) jewelries..

문제 보러 가기! NXN의 표에 수가 채워져있고, 모든 수는 자기 한 칸 위의 수보다 크다. N번째 큰 수를 찾는 문제이다. (N은 1~1500이다.) 처음 - 메모리 초과 처음에는 extend를 이용해서 1차원 리스트로 N^2개의 값을 다 받았다. 이 문제에서 N번째로 '큰!!" 수를 찾아야 하므로 최대 우선순위 큐로 쓰려고 했다. 그래서 -1을 곱해서 넣어줬다. 그 후, 그 리스트를 우선순위 큐로 만들었다. heapq.heappop을 N번해서 N번째값을 출력했다. -1를 곱해서 넣어줬으니까, 출력할 때 -1을 곱한 후에 출력했다. 예제는 맞는데, 메모리 초과가 나왔다.. 1500 X 1500 = 2250000 개를 리스트로 만들고 힙으로 만드는 게 너무 힘든가.. import sys, heapq in..

문제 보러 가기!! 재밌는 이분 탐색 문제였다~ 처음에 left를 0, right를 A로 삼고 이분 탐색을 시작했다. 상근이가 내는 전기 요금이 mid라고 가정하고, 아래 계산이 맞는지 봤다. 1. 상근이가 내는 전기 요금을 가지고, 상근이가 쓴 전기 사용량을 계산한다. 2. 상근이가 쓴 전기 요금에 B를 더하면 이웃이 쓴 전기 요금이 된다. 이를 가지고 이웃이 쓴 전기 사용량을 계산한다. 3. 상근이가 쓴 전기 사용량과 이웃이 쓴 전기 사용량을 합쳤을 때 내야 하는 요금을 계산한다. 4. 3번의 결과와 A를 비교한다. 4-1. 같으면 정답이다! 4-2. 3번의 결과가 A보다 더 크면, 상근이가 쓴 전기 요금(mid)을 낮추어야 한다. 4-3. 3번의 결과가 A보다 더 작으면, 상근이가 쓴 전기 요금(m..

문제로 가기! 인사 요즘 싸피 pjt를 하다가 오랜만에 문제 푸니 좋다~ 꾸준히 풀어야 하는데...!! 설명 처음에는 모든 각도를 계산해야 하나..? 어떻게 계산하지..? 하다가, 기울기를 구하면 된다는 걸 알았다. 그런데 딱 나누어서 떨어지지 않는 것(무한 소수 -> 10/3 = 3.33333333333......)이 문제가 된다고 한다. 이 블로그를 보고 알았다 !! 그래서 x, y를 최대한 약분한 것을(0,0에서 시작하므로) 튜플에 넣어서, 기울기로 봐줘야 한다. 딕셔너리(역시 default dictionary가 너무 편하다 >< )에 그 기울기를 key로 삼아서, 그 기울기를 만날 때마다 1씩 더했다. 나중에 딕셔너리.value()를 이용해서, 값들을 봐주면서 제일 큰 값을 정답으로 출력했다. 헷..

문제 보러 가기! 구현 문제! 처음에는 엄청 간단하게만 생각했는데, 아니었다. 생각해야 할 게 많았다.. 나는 한 명씩 거짓말쟁이로 가정하고, 정답이 될 수 있는 것들을 다 모았다. 정답이 될 수 있는 게 하나라면, 정답으로 출력하면 된다. 정답이 될 수 있는 게 없거나, 여러 개라면 정답이 확정이 안되는 것이니까 -1를 출력하면 된다. 한 명을 거짓말쟁이로 가정한 상태에서 정답이 뭐가 될 수 있는지 봐주기 위해서, 매번 baseman_arr 리스트를 만들었다. 1번~ 9번에 대해서, 1루수라고 하는지 아니라고 하는지를 저장했따. 초기값은 -1로 해둔 후에, 해당 번호의 사람이 1루수라고 하면 1을, 아니라고 하면 0을 저장했다. 모순이 생긴다면 바로 break를 했고, 그렇지 않다면 모든 사람의 말을 ..

문제 보러 가기! 평범한 다익스트라 + 알파이다. 최소 비용을 가지는 경로를 방문 도시 순서대로 출력하는 부분, 그 경로에 포함되는 도시 개수도 출력해야 해서 좀 더 생각해야 했다. distance 리스트를 활용했다. 평범한 다익스트라에서는 distance 리스트는 출발점에서 그 점까지의 비용만 저장한다. 그런데 여기에서는 출발점에서 그 점까지 최소 비용으로 올 때, 그 전 점도 저장했다! 다익스트라를 다 수행한 후에, 최종 도착 점부터 distance 리스트를 활용해서 거꾸로 봐주었다. 그 전에 어떤 점에서 왔는지를 봐서 history 리스트에 저장한 후, 거꾸로 출력했다. [TMI 잠깐 근황] 요즘 싸피에서 프로젝트를 열심히 하느라고 ㅠㅠ 문제를 별로 못풀다가 푸니까 재밌다 >< (물론 프로젝트도....

문제 보러 가기! 문제 2행 n열에 한 칸마다 스티커가 있다. 각각에는 점수가 있다. 한 스티커를 쓰면, 그것과 변을 공유하는(상하좌우) 스티커를 못 쓴다. 쓸 수 있는 스터커 점수의 최댓값을 구하는 문제였다. 풀이 DP로 풀었다. dp 테이블을 2Xn 리스트로 만들었다. 그 위치의 스티커를 뗐을 때, 그때까지의 최대 점수를 저장한다. 1행 n열의 스티커 뗐을 때의 최대 점수 = (2행 n-1열 스티커 뗐을 때의 최대 점수 or 2행 n-2열 스티커 뗐을 때의 최대 점수) + 1행 n열 스티커 점수이다. 2행 n열의 스티커 뗐을 때의 최대 점수는 위의 식에서 2행을 1행으로, 1행을 2행으로만 바꾸면 된다! n이 1일 때, 2일 때는 따로 수작업으로 처리했다. 하늘색 숫자는 그 자리의 스티커 떼면 얻는 ..

문제 보러 가기! 문제 1n의 수로 이뤄진 수열이 주어진다. 1n까지 수를 순서대로 스택에 넣었다 뺐다 하면서 주어진 수열을 만드는 방법을 출력해야 한다. 풀이 처음에는 막막했는데, 스택의 성질을 생각하면서 구현했더니 됐다 ! 스택 - Last in First out!! import sys input = sys.stdin.readline MIIS = lambda: map(int, input().split()) n = int(input()) arr = list(int(input()) for _ in range(n)) # 입력된 수얼 ans = [] stack = [] idx = 0 # 입력된 수열 어디까지 만들었는지 for i in range(1, n+1): stack.append(i) # 스택에 넣는다 ..