오늘의 문제 : https://www.acmicpc.net/problem/10217 안뇽하세요. 오늘은 김찬민 씨를 위해 LA로 가는 비행기 편을 알아봐야 합니다. 알아봐 주면 혹시 짐꾼으로 데려가주지 않을래? 정답률이 10%인 문제라서 긴장하고 풀었습니다. 1번에 N번 노드까지의 사용가능한 비용 안에서 최소 도달 시간을 구해야합니다. 비용도 양수이고 출발점과 도착점이 정해져 있어서 다이젝스트라 알고리즘을 사용하면 됩니다. 근데 문제가 있습니다. 다이젝스트라 알고리즘이 야무진 이유가 "첫 방문이 최단거리" 라는 기가 막힌 조건이라고 생각합니다. 하지만 현재 문제에서는 그 조건이 성립하지 않습니다. 위 그래프에서 3번까지의 최단 시간은 2이지만, 만일 사용가능한 비용이 5라면 4가 됩니다. 즉 1번에..
오늘의 문제 : https://www.acmicpc.net/problem/1082 분명 하루 딱 한 문제만 푸는데 이렇게 어려울 수가.. 요즘 다시 알고리즘의 절망 계곡에 들어선 것 같습니다. 제 자심감의 봉우리는 너무 금방올라가서 탈입니다. 아는 것이 힘이지만, 살짝 아는 것은 고통이군요. 문제 풀겠습니다. 처음 접근은 그리디로 했으나, 조건을 코드로 구현하는 것이 어려워서 다이내믹 프로그래밍을 사용하여 풀었습니다. 저는 사용한 비용을 통하여 점화식을 세웠습니다. DP[n] = Math.max(DP [n] , DP [n - 사용가능 한 비용] + 사용한 숫자(String)..) 사용가능 한 비용이 최대 n개가 되지만, 문제 조건을 보면 최대 비용이 50이라 그냥 했습니다. 그리고 이제 사용가능 한..
오늘의 문제 : https://www.acmicpc.net/problem/20440 아니 모기송하면 이광수 님의 모기송 아닌가요?나참. 처음에는 PQ를 사용하여 도전을 해봤는데 계속 실패해서 다른 분의 코드를 흡수헀습니다. HashMap을 사용하여 특정 시간에 모기가 얼마나 들어고 나갔는지를 저장하는 방법입니다. HashMap을 사용한 이유는 모기가 들어오고 나간 시간 사이는 탐색을 할 필요가 없어서 라고 생각합니다. 예를 들어 1,20에 모기가 들어왔다면, 그 사이 수 2,3,4,.. 19는 다 같은 모기 수를 갖고 있음으로 탐색할 필요가 없습니다. 문제에서 시간의 최대 값를 21억으로 말한 것도 힌트가 될 수 있겠습니다. 구현은 간단합니다. 코드import java.io.BufferedRea..
오늘의 문제 : https://www.acmicpc.net/problem/1943 그리디로 풀다가 실패해서 백트래킹으로 다시 도전 후 또 실패하고 정답을 맞힌 문제입니다. 1. 그리디 동전을 내림차순으로 정렬 후 현재 더 적은 금액을 가지고 있는 사람에게 동전을 주도록 하였습니다. 그럴 듯 하지만...313 13 12 8위와 같은 상황에서는 적절하지 못하게 동전을 분배합니다. (제가 직접 생각했어요 뿌듯) 2. 백트래킹 모든 경우를 전부 확인해야 한다고 생각하여, 백트래킹을 통해 확인했습니다. 하지만 테스트 케이스 3개 * 2의 n*n(대략)의 시간복잡도가 나오기 떄문에 시간을 초과하게 됩니다. - 백트래킹 코드import java.io.BufferedReader;import java.io.IOEx..
문제 : https://www.acmicpc.net/problem/4933 혹시 문제를 풀기 전에 모호한 부분이 많아서 시도를 못하신 분들은 아래 글을 읽어 보고 다시 도전해 보세요! + 문제 부연 설명 "두 트리가 같다"에 대해 - '두 트리가 같다'는 부모 내 자식들의 자리를 바꿔서 같은 트리가 된다면 같은 트리입니다. - 구조는 같지만 같은 위치의 정점 이름(A, B..) 이 다른 경우에 대해서는 과감하게 같지 않은 트리라고 생각하셔도 됩니다. 입력 범위에 대해. - 모든 채점 결과에 대해(지금 기준) "시간초과"가 나온 적이 없는 문제입니다. 크게 신경 쓰지 않으셔도 됩니다. 혹시 저만 모호하다고 생각했나요..? 그럼 이제 문제를 풀어보겠습니다. 문제를 정리해 보자면 입력받은 값으로 트리..
오늘의 문제 : https://www.acmicpc.net/problem/20055 조건을 확실하게 정리하는 습관을 기릅시다. 왜 와이? 요번문제에서 바로 코딩 들어가서 삽질을 좀 했기 때문이죠. 투 포인터 및 구현문제입니다. 1. 작업의 순서 1) 벨트가 돌아간다. 로봇이 끝부분에 도달하는 즉시 벨트에서 나온다. 시작점과 끝점을 -1 시켜 벨트의 회전을 구현. 2) 로봇이 이동한다. 3) 로봇이 추가된다. 현재 추가할 경로의 내구도가 0인 경우 패스. 현재 추가할 경로에 로봇이 이미 있다면 패스. 2. 로봇의 이동 상황 구분. 1) 이동할 로봇이 이미 끝부분에 있는 경우 즉. 시 제외. 2) 이동할 로봇의 다음경로에 이미 로봇이 있는 경우 원래 위치 그..