Dalin's Archive

문제 풀러 가기 문제가 참 재밌다..ㅋㅋㅋ 그리디로 풀었다. 쭉~~ day 리스트에 튜플로 정보를 입력받았다. 이때 꼭 시작해야 하는 날(꼭 끝내야 하는 날 - 과제할 때 걸리는 일수 +1)을 구해서, (이날에는 꼭 시작해야 하는 날, 과제 할 때 걸리는 일수, 이때까지 꼭 끝내야 하는 날)형식의 튜플을 만들어서 리스트에 넣었다. 리스트를 정렬하는데, 꼭 끝내야 하는 날 기준으로 내림차순으로 정렬했다. 오늘로부터 먼 순서대로 과제를 해야, 내일부터 가장 오랫동안 놀 수 있는 날을 구할 수 있으니까. now는 과제를 시작하는 날을 의미한다. 일단 첫번째 과제를 시작하는 날은, 최대한 늦게 시작하는 게 좋으니까, 과제를 꼭 시작해야 하는 날로 초기화해서 시작한다. 그 다음부터는 두번째 과제부터 마지막 과제까..

문제 보러 가기!!! 예전에 틀린 코드💫 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개 없애자!! 그리고 나머지 간격들..

문제 보러 가기! 풀이 🎊 모든 강연 요청을 (요금, 일자) 형식의 tuple로 이뤄진 리스트에 저장했다. 일자 -> 요금이 큰 순서대로 정렬했다. d일 안에 강연을 해야 한다는 것에 대해 생각해보자. d가 7이라면, 1일 안에 강연해도 되고 2일 안에 해도 되고 3일 안에 해도 되고 .... 7일 안에 강연해도 된다는 뜻이다. 만약 d가 1이라면 1일 안에 강연해야만 돈을 준다는 뜻이다. => 일자가 큰 순서대로 봐준다!! 일자가 큰 순서대로, 그 일자에 가능한 강연의 비용을 우선순위 큐에 넣는다. (같은 d로 요청한 강연이 여러 개라면 모두 넣는다) 그 후 각 일자마다 보면서, 그 일자에 강연을 한다고 했을 때 돈을 가장 많이 주는 강연을 한다. (우선순위 큐에서 heappop) 주의점 👻 heapq..

문제 보러가기! 풀이 🌷 지문이 웹툰 내용 같고 재미있었다 ㅋㅋ 핵심은 슬라임 에너지가 적은 슬라임을 두 개씩 합성하는 것이다!! 그걸 파악한 후에는 카드 정렬하기 문제와 비슷하게 풀었다. 카드 정렬하기 문제에서는 더하기라면, 이 문제에서는 곱하기라는 점 정도만 다른 것 같다. 아래와 같이 풀었다. 처음 슬라임을 리스트로 받은 후에 heapify하기 청구될 전기 에너지 초기값은 1로 시작하기(곱의 항등원은 1이므로) 힙의 길이가 2 이상일 동안은(즉, 슬라임이 두 개 이상일 때) 힙에서 슬라임 에너지가 적은 슬라임을 두 개 꺼낸다. 각각 슬라임 에너지가 A, B 라고 하자. 그 둘을 곱하면 슬라임 에너지가 AXB인 슬라임이 되고, 그걸 힙에 넣는다. 또 청구될 전기 에너지에 A X B한 값을 곱한다. 힙..

문제!! 풀이 🌷 통나무의 세로로 입력으로 들어오지만 가로만 봐주면 된다. 선 긋는 스위핑 문제처럼 풀면 되는 것이었다. 그 문제 포스팅은 여기..ㅎㅎ 어려웠던 점 🦄 처음에는 통나무의 가로, 세로 좌표 둘 다 봐줘야 하는 줄 알았다.. 좌표는 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..

문제 보러 가기~ ㅠㅠㅠ 그리디 문제는 아이디어 떠올리기가 어려워서 다른 분들 것을 참고할 때가 많았다.. 그러다가 오랜만에 스스로 푼 문제..!! 접근 일단 문제에서 구할 것은 '우울함의 합'을 최소화하자는 것이다. 우울함은 기분 0 미만인 날에서 (기분)^2이다. 약속의 순서는 바꿀 수가 없이 언제 할지 배치하는 것이다. 일단 기분이 0 이상이면 괜찮은 상황이다. => 모든 날의 기분이 0 이상일 수 있으면 정답은 0이다. => 모든 날의 기분이 0 이상일 수 없으면, 약속이 몰려 있어서 외로움이 극대화되는 것보다는 (약속이 쭉 있다가 약속 없는 날이 연속 4일이 되는 경우에, 외로움은 1의 제곱+ 2의 제곱+ 3의 제곱+ 4의 제곱이 된다.) 기분의 제곱을 해서 우울함 수치를 구하니까..

문제 보러 가기! 아이디어 ❄ N자리 숫자가 주어졌을 때, 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 만드는 문제였다! 처음에 한 생각은, '아! 그러면 쭉 보면서 작은 숫자 K개를 없애주면 되려나?' 였다. 1924에서 2개를 지우라고 하면, 가장 작은 숫자 1과 2을 없애면 94가 되는 예제를 보고 한 생각이었다. 그런데 4177252841에서 4개 숫자를 지우라고 하면 어떨까? (예제 3번) 작은 숫자 순서대로 4개.. 1, 2, 2, 1를 없애면 477594가 된다. 이는 정답은 775841과 다르다!! 이건 아니었다.. 그래서 다시 생각해봤다. 그랬더니 가장 큰 수가 되려면, 앞의 자리가 큰 게 중요하다는 것이 생각났다! 그래서 맨 앞부터 보면서, 그게 그 다음 숫자보다 작으면 없애는 식으..