문제https://www.acmicpc.net/problem/1781 문제 풀이처음 문제를 보고 난이도에 비해 정말 쉽다고 생각했다.회의실 배정과 유사하게 우선순위큐를 사용해서, deadLine이 짧은 순, 가치가 무거운 순으로 정렬한 뒤, 시간에 맞게 빼면 된다고 생각했다. 우선 문제에 대한 테스트케이스는 다음과 같다.해당 작업들을 우리가 목표로 하는 최대의 가치의 순서로 작업할 수 있도록 정렬해줘야 한다.고려해야할 점은 다음과 같다.데드라인이 적은 순서대로 정렬을 한다.가치가 많은 순으로 정렬을 한다.위 조건을 고려해서 정렬을 하면 다음과 같다.그리고 데드라인 별로 작업을 선택해서 답을 구하면 된다.하지만 여기서 함정이 존재한다.내가 풀이했던 방식은 데드라인이 아니라, 그때 풀어야 했던 문제라고 생각..
문제 https://www.acmicpc.net/problem/1445 1445번: 일요일 아침의 데이트 첫째 줄에 숲의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 3보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 숲의 지도가 주어진다. 숲의 지도는 S, F, g, . 만으로 이루어져 있 www.acmicpc.net 문제 풀이 나는 해당 문제를 전형적인 bfs 문제라고 생각한다. 하지만 bfs 문제에서도 조금 더 진화한 문제이다. 우선 문제 초기에는 DP를 사용해서 주변에 존재하는 쓰레기를 저장해서 방문 처리를 하려고 했지만, 결과적으로 도착지점에 도착한 경우에 최적의 도착을 해야하기 때문에, 도착한 시점에 우리는 가장 적은 쓰레기를 마주치고 밟아야 한다. 그렇기 때문에 DP..
문제 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 🔎문제 설명 문제만 보고 이게 DP문제인가? 싶었다. 그냥 무작정 BFS를 사용해서 풀었다. 그랬더니 시간초과가 났다. 이동하는 조건만 맞으면 큐에 넣어줬고, 도착지점에 도착한다면 그게 적절한 이동이라고 생각해서, 결괏값을 계속 더해줘서 함수를 탈출한다면 결과값을 출력해 줬지만 아마 배열 크기도 크고, 큐에 쓸데없는 없는 값이 많이 들어가서 그런 거 같다. 다른 사람들의 풀이를 보니 dfs..
