분류 전체보기414 백준 17845 수강 과목 문제 URL : https://www.acmicpc.net/problem/17845 17845번: 수강 과목 첫줄에 서윤이의 최대 공부시간 N (1 ≤ N ≤ 10,000), 과목 수 K (1 ≤ K ≤ 1,000)이 공백을 사이에 두고 주어진다. 이후 K개의 줄에 중요도 I (1 ≤ I ≤ 100,000), 필요한 공부시간 (1 ≤ T ≤ 10,000)이 www.acmicpc.net 문제 접근법: 배낭문제이지만 dfs+메모이제이션으로 활용해서 풀수있는문제입니다. 메모리는 10000*1000 이라 1천만까지는 괜찮기때문에 메모이제이션이 c++에선 가능하지만 똑같이 코딩했는데 python에서 시간초과가 나더군요 파이썬은 dfs + 메모이제이션이 힘든것같습니다. 처음에 파이썬으로 풀어서 시간초과 나길래 어딜.. 2023. 12. 12. 백준 20303 할로윈의 양아치 문제 URL : https://www.acmicpc.net/problem/20303 20303번: 할로윈의 양아치 첫째 줄에 정수 $N$, $M$, $K$가 주어진다. $N$은 거리에 있는 아이들의 수, $M$은 아이들의 친구 관계 수, $K$는 울음소리가 공명하기 위한 최소 아이의 수이다. ($1 \leq N \leq 30\ 000$, $0 \leq M \leq 100\ 000$, www.acmicpc.net 문제 접근법 : union & find + dfs dp(배낭문제) 문제입니다. 한사람의 사탕을 뺏으면 그친구것도 동시에 뺏기는거니 집합으로 표현합니다. 그림으로 그리게되면 이러한 그림이 형성됩니다. 총4개의 집합이 만들어집니다. 그렇게이 (4,9) 가있는 집합과 (7,8)이 있는의 집합을 뺏어서 .. 2023. 12. 12. 백준 14728 벼락치기 문제 URL : https://www.acmicpc.net/problem/14728 14728번: 벼락치기 ChAOS(Chung-ang Algorithm Organization and Study) 회장이 되어 일이 많아진 준석이는 시험기간에도 일 때문에 공부를 하지 못하다가 시험 전 날이 되어버리고 말았다. 다행히도 친절하신 교수님께서 아래와 www.acmicpc.net 문제 접근법: dfs+ 메모이제이션 문제 입니다. 내가 가지고있는 시간으로 풀수있는 문제는 풀거나 혹은 안풀고 다른문제로 넘어가거나 하여 모든 경우의수를 dfs로 풀면됩니다. 그리고 메모이제이션을 이용해서 가지치기를 하면 쉽게 풀수있는 문제입니다. 파이썬으로 푼 문제입니다. 소스코드 : import sys sys.setrecursionl.. 2023. 12. 11. 백준 1106 호텔 문제 URL : https://www.acmicpc.net/problem/1106 1106번: 호텔 첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 www.acmicpc.net 문제 접근법 : dfs + 메모이제이션문제입니다. 홍보를 할땐하더라도 비용이드는 최소가 되도록 전수 조사로 재귀를 짜시면됩니다. 그후 메모이제이션으로 가지치기를 하시면 쉽게 해결할수있는 문제입니다. 파이썬 으로 쉽게할수있는 문제라 파이썬으로 풀었는데 재귀깊이가 n= 20이라 100만까지 갈수있으니 재귀 깊이를 늘려줘야한다는거 잊지마시길 소스코드 : import sys sys.s.. 2023. 12. 11. 이전 1 ··· 13 14 15 16 17 18 19 ··· 104 다음
