Dalin's Archive

문제 보러 가기!!! 예전에 틀린 코드💫 DFS로 풀려고 했던 듯. 예제는 맞추는데, 채점을 하면 메모리 초과가 난다. import sys sys.setrecursionlimit(10**6) def DFS(depth,score): if depth==k: if score>0: A.append(score) else: DFS(depth+1,score+L[depth]) DFS(depth+1,score) if __name__ == "__main__": k=int(input()) L=list(map(int,input().split())) A=[] DFS(0,0) A=list(set(A)) for i in range(1,max(A)): if i not in A: print(i) break 정답 코드 💟 아이디어가 정..

전에 한 코테에서 쓴 맛을 본 후로.. 백준에서 문제를 풀 때 분류를 안 보고 있다! 문제 풀이를 생각해낼 때 시간이 더 오래 걸리긴 하지만, 그래도 그만큼 더 생각하게 되는 것 같다!! 문제 보기 이 문제를 풀 때 한 생각들의 흐름, 풀이 한 위치에 여러 센서가 설치될 수 있다. 그렇지만 그럴 때 하나만 고려하면 된다. -> set을 이용해서 중복을 제거함. 각 센서의 번호 같은 건 중요하지 않다. 센서들을 정렬해서 봐야 겠다. -> sort 각 집중국의 수신 가능 영역의 거리 합이 최소가 되려면, 각 집중국 센서 수신 가능 영역의 시작점과 끝점은 센서 있는 곳인 게 좋겠다. 각 집중국 센서 수신 가능 영역이 조그마한 게 좋다 -> 센서 사이 간격이 큰 순서대로 K-1개 없애자!! 그리고 나머지 간격들..

문제!! 풀이 🌷 통나무의 세로로 입력으로 들어오지만 가로만 봐주면 된다. 선 긋는 스위핑 문제처럼 풀면 되는 것이었다. 그 문제 포스팅은 여기..ㅎㅎ 어려웠던 점 🦄 처음에는 통나무의 가로, 세로 좌표 둘 다 봐줘야 하는 줄 알았다.. 좌표는 10^9까지 있다고 하는데, 가로 세로를 고려해서 2차원으로 만들면 너무 클 것 같은데... ㅠ 어떻게 하나 고민했다. 그런데 가로!!!만 봐주면 되는 것이었다. 점프하면 되니까 세로는 볼 필요가 없었다. 원래 입력 받은 리스트를 정렬해서, 그 순서가 망가진다.. 그러니까 원래 인덱스를 가지고 있어야 한다! 그래야 어떤 통나무랑 다른 통나무랑 이어져있는지 체크가 가능하니까!!! 코드 🐸 import sys input = sys.stdin.readline N, Q ..

문제 보러 가기! 처음 풀이- 시간 초과 🎇 가방 많이 넣을 수 있는 것부터 하나씩 보면서, 보석을 가격 비싼 순(가격 같으면 무거운 순)으로 봤다. 그 가방에 보석을 넣을 수 있으면, 보석 없애고 가방도 없애고.. 그 가격을 정답에 더했다. 그 가방에 그 보석을 못 넣으면 그냥 보석을 없앴다. (어차피 이후 가방에도 그 보석이 무거워서 못 넣으니까) 예제는 맞기는 한데,, 그랬더니 시간 초과 ㅠ 코드는 이랬다. 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..

문제 풀러 가기! 재미있는.. 그리디 문제였다.. ^^ 일단 입력을 받는다. 0, 0 이 나올 때까지 받으니까 while을 이용했다. 혹시 몰라서 출발점과 끝점이 같으면 받지 않았고, 출발점이 음수이고 끝나는 점이 0 이하이면 받지 않았다. 그리고 정렬~ 출발점 빠른 순 -> 출발점이 같으면 끝나는 점이 빠른 순으로 정렬했다. 그 후에 그 상황에서 끝나는 점의 좌표(finish_idx)와 사용한 선의 개수를 0으로 초기화했다. 그리고 쭉~~ 봤다. 그러면서 finish_idx보다 일찍 시작하는 선분을 후보에 넣었다. 그리고 그 중에 끝나는 좌표가 제일 큰 선분을 사용하는 게 이득이니까! 제을 큰 끝나는 좌표를 finish_idx에 대입하고, 사용한 선의 개수를 1 더했다. 만약에 finish_idx가 M..

문제로 가기 정렬하고 쭉 ~ 한번 보면 되는 스위핑 문제!! 정렬한 후에 (출발지가 앞쪽인 순서, 출발지가 같으면 도착지가 앞쪽일 수록 앞에) 쭉~ 보면서 두 노선씩 비교한다. a_route는 처음 노선으로 초기화하고 시작하고, b_route는 그 다음 노선부터 끝까지 쭉 본다. 만약 a, b 노선이 겹친다면 합쳐서 새로운 노선으로 만든다! 이때 요금은 더 낮은 쪽을 따른다. 출발점이 더 나중에어도, 도착점이 더 이른 노선이 있을 수도 있다. 노란 색 노선, 빨간 색 노선을 비교할 때는.. 일단 겹치니까 a_route를 업데이트하는데, 'a_route = (a_route[0], max(a_route[1], b_route[1]), min(a_route[2], b_route[2]))'에서 'max(a_rou..

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

문제 보러 가기! 얼마 전에 누적합을 처음 공부하고, 관련된 문제를 풀고 싶어서 스터디 문제에 추가했다.(한 사람 당 한 문제씩 추가하는 방식으로 스터디를 하는 중입니다~) 그런데 단순한 누적합..만으로는 해결할 수 없었다..ㅠㅠ 0 ≤ 모기의 입장 시각 < 모기의 퇴장 시각 ≤ 2,100,000,000... 너무 컸기 때문이다. 그래서 계속 시간 초과, 메모리 초과..와 싸우다가 스터디를 할 때까지 못 풀었다. 스터디원 분께서 설명해주셔서 값, 좌표 압축이라는 아이디어를 처음 알게 되었다! 그 아이디어를 적용하고, 다른 부분도(이것도 아래에서 설명하겠다.) 바꾸니까 문제를 풀 수 있었다 ! 전에 코드(시간 초과) 💥 import collections import sys input = sys.stdin...