https://www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net 물통이 3개로 고정되어 있고 물을 옮길 수 있는 경우 역시 고정되어 있었기 때문에 고려해야 할 경우의 수가 정해져 있다고 생각했다. A가 비어있을 때 C에 들어있는 물의 양을 찾고자 했다. 하지만 이 문제를 어떻게 탐색으로 풀어야 할지 모르겠어서 답안을 참고했다. 이 문제는 완전탐색(BFS)을 통해 고려한 경우의 수는 하나씩 제외시키면서 풀어야 한다. 고려한 방식을 제외시키는 ..
https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 문제를 간단히 정리하면 과제를 최대한 미루면서 가장 높은 점수를 받기이다. 즉, 마감일이 4일 남았으면 1, 2, 3일 남은 과제들을 하는 것이 이득이다. 4일 남은 과제의 점수가 제일 높다고 해서 1일차에 4일 남은 과제를 해버리면 1일 남은 과제의 점수를 날리게 된다. 어차피 모든 과제는 하루가 소요되기 때문에 마감일과 점수만 판단하면 된다. 내가 처음에 시도한 방법은 아래와 같다. (잘못된 방법) 점수 내림차순으로 정렬한 뒤 0번 인덱..
https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 시험기간이라 그런지 알고리즘 푸는 게 더 재밌다..ㅠ 이 문제는 처음에 이해를 못해서 건너뛰었다가 다른 투포인터 문제를 푼 후에 다시 도전한 문제다. 처음에 착각한 부분이 있었는데, 4도 다른 수로 표현이 가능하길래 2 + 2가 되는 줄 알고 1 + 1 = 2도 가능할 줄 알았다. 그런데 문제를 잘 읽어보면 라고 명시되어 있다. 즉, 4는 2+2가 아니라 1+3이 가능해서 "좋다"에 포함되는 것이다. 이후 문제를 다시 잘 파..
https://www.acmicpc.net/problem/2230 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net 처음에 정렬로만 풀었다가 시간초과가 났다. 이후 두 수를 고른다는 조건을 파악하여 투 포인터로 풀었다. 위 문제들이랑 결이 비슷해서 어렵지 않게 풀 수 있었다. 입력받은 숫자들을 빈 배열에 추가해 준다. 배열을 정렬한다. 인덱스를 늘리며 두 수의 차를 구한다. 두 수의 차가 m 미만인 경우, right 인덱스에 1을 더하여 더 큰 차이가 나도록 만든다. 두 수의 차가 m 이상인..
https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 누적합은 익숙하지 않아서 항상 오래 걸린다. 이 문제는 DP까지 적용해야 했기 때문에 더 오래 걸렸다. 문제를 봤을 때 풀어야할 방법이 바로 생각 나서 구현했지만.. 코드만 봐도 시간 초과가 무조건 날 것 같았다. 그리고 당연히 시간 초과가 났다. 시간 초과 코드 import sys input = sys.stdin.readline n, m = map(in..
https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 백준 1717번 '집합의 표현'을 풀었다면 약간의 코드 수정으로 풀 수 있다. 유니온 파인드 문제들은 대부분 결이 비슷한 것 같다. 정답 코드 import sys input = sys.stdin.readline def find(a): if a == parent[a]: return a parent[a] = find(parent[a]) return parent[a] def union(a, ..
