https://www.acmicpc.net/problem/1315 이 문제는 N개의 퀘스트가 주어질때 각각의 퀘스트에 필요한 요구치가 주어진다 이는 STR[i], INT[i]가 주어지며 퀘스트를 완료하기 위해서 현재 나의 스텟 중에 하나 이상이 퀘스트가 요구하는 스텟보다 크면 완료할 수 있으며 보너스로 스텟을 찍을 수 있는 포인트를 준다.이때 최대로 완료할 수 있는 퀘스트의 개수를 구하는 문제이다. 스스로 해결: ❌ 접근방법어느정도 dp를 사용해서 풀어야하는 것은 알았지만 식을 어떻게 세워야할줄 몰랐다. 현재 내가 할 수 있는 행동은 각 퀘스트마다 내 스텟과 비교하여 완료할 수 있으면 다음퀘스트를 완료할 수 있는 가능성이 높아지기 때문에 무조건 완료하는것이 좋다고 생각하였다 또한 퀘스트 완료후 보너스 ..

https://www.acmicpc.net/problem/1132 이 문제는 N개의 수가 주어지고 N개의 알파벳이 주어질때 각 알파벳에 0부터 9까지 사상시켜 최댓값을 만들어야 하는 문제이다. 처음엔 모든 경우의 수를 다 찾는 방법밖에는 없다고 생각하여 주어진 알파벳들을 백트래킹을 사용하여 다 탐색하여 최댓값을 리턴하는 방식을 사용했지만 N이 최대 50이며 알파벳이 10개가 입력된다고 가정했을때 시간복잡도는 O(10! * N)으로 1억을 가뿐히 넘긴다. 따라서 다른 방법으로 접근해야 하는데 결국 알파벳의 각 자리수가 존재하기 때문에 이를 이용해서 그리디하게 풀어보았다. 먼저 첫번째 테케 ABC, BCA의 예시를 보자A는 100의 자리 1의 자리가 존재하여 총 101이다 B는 10의 자리 100의 자리..

https://www.acmicpc.net/problem/14464 문제 이해이 문제는 C개의 닭과 N개의 소가 주어진다. 이때 각 닭들은 c초에 길을 건널 수 있으며 각 소들은 a, b가 주어지며 a부터 b까지 길을 건널 수 있다. 이때 닭은 소가 길을 건너줄 수 있는걸 도와줄 수 있으며 a 문제 접근 처음엔 이분탐색을 사용하여 소의 시간을 끝시간에서 부터 시작 시간까지 탐색하려고 했지만 주어지는 시간이 10억이기에 불가능하다고 생각했다 따라서 오름차순으로 정렬하여 시간이 매칭될때 하나씩 더해주는 방법을 생각하였다. 하지만 반례를 생각해보면 무조건 시간이 매칭된다고 하나씩 더해주면 안된다 닭 : 5, 100소 : (1, 100), (4, 6)인 경우 5인 닭이 (1, 100)이 매칭이 된다 하지만 ..

https://www.acmicpc.net/problem/9489 이 문제는 N개의 노드 수와 사촌을 구해야 하는 K노드가 주어진다. 이후 트리의 관계가 주어질때 특정 노드 K의 사촌의 수를 구해야 한다. 이 문제에서 사촌이랑 두 노드의 부모는 다르지만, 두 부모가 형제일때 두 노드를 사촌이라고 한다. 위 사진에서 노드 15를 기준으로 부모는 4이며 부모 4의 형제는 3과 5이다.즉 3의 자식들과 5의 자식들은 노드 15와 사촌의 관계가 성립되기 때문에5가 출력되어야 한다. 그렇다면 8, 9, 15, 30, 31, 32의 노드들의 공통점은 무엇일까?? 자세히 살펴보면 부모의 부모 즉 2단계의 부모는 1로 같다. 따라서 부모의 부모가 같으며 해당 노드의 부모가 다르면 사촌이 성립된다는 것이다. 정답코드#..

https://www.acmicpc.net/problem/17835 이 문제는 N개의 노드와 M개의 양방향 간선이 주어지고 K개의 면접장의 수가 주어진다. 이때 K 노드를 제외한 모든 노드에서 K개의 노드에 최단거리중 가장 먼 거리와 노드를 찾는 문제이다. 노드의 개수와 간선의 개수는 최대 10만과 50만으로 다익스트라를 K번 최대 10만번 수행하기에는 시간초과가 난다.O(N * N log M) 그렇다면 O(N log M) 한번으로 풀 수는 없을까?? 생각을 다르게 해봐서 K개의 노드를 시작점으로 잡고 해당 노드를 제외한 모든 노드의 최단 거리를 알 수 있다. 시작점(N개 노드) -> 도착점(K개 노드) 이 문제를 시작점(K개 노드) -> 도착점(N개 노드)로 변화하여 풀 수 있다는 말이다. 따라서 K..