https://www.acmicpc.net/problem/18310 18310번: 안테나 첫째 줄에 집의 수 N이 자연수로 주어진다. (1≤N≤200,000) 둘째 줄에 N채의 집에 위치가 공백을 기준으로 구분되어 1이상 100,000이하의 자연수로 주어진다. www.acmicpc.net 처음에는 그리디 문제라는 걸 깨닫지 못하고.. 거리를 직접 구해서 비교하려고 하다가 그림을 몇 번 그려보니.. 그냥 정렬을 해서 중간 값을 출력하면 된다는 것을 깨달았다. 이렇게 간단하게 풀리는 문제였다니! 항상 그리디를 의심하자.. import sys input = sys.stdin.readline N = int(input()) house = list(map(int, input().split())) house.sort..
알고리즘💻/그리디
https://www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 0과 1이 모여있는 집단(?) 의 갯수를 구해서 더 적은 쪽을 출력하면 되는 문제였다. cnt = [0, 0] 을 만들어서 주어진 문자열을 순회하면서 앞의 문자와 뒤의 문자가 달라질 때마다 해당하는 인덱스에 카운트를 했다. 이때 주의할 점은 '0011' 과 같은 경우에 마지막 11이 카운트가 되지 않기 때문에 주어진 문자열의 맨 뒤에 '2'를 추가해서 무조건 카운트가 되도록 했다. import s..
https://www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 아이디어를 찾는 게 꽤나 어려웠던 문제이다. 처음에는 가격을 그래프로 그렸을 때 꼭짓점을 찾아서 꼭짓점의 앞에서 주식을 사고 꼭짓점에서 팔고, 또 계속 사다가 다음 꼭짓점에서 팔고 이런 식으로 하면 되지 않을까? 싶었지만 꼭짓점이 고점이 아닌 경우 해당 지점에서 주식을 매도하는 것보다 주식을 매수하는 게 더 이득이 크기 때문에 해당 접근 방식은 틀렸다. 단순하게 다시 생각해보니, 일단..
https://www.acmicpc.net/problem/9009 9009번: 피보나치 입력 데이터는 표준입력을 사용한다. 입력은 T 개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 수를 나타내는 정수 T 가 주어진다. 각 테스트 데이터에는 하나의 정수 n www.acmicpc.net 하나의 양의 정수가 주어질 때, 피보나치 수들의 합이 주어진 정수와 같게 되는 최소 개수의 서로 다른 피보나치 수들을 구하라. 이때 피보나치 수는 증가하는 순서대로 출력 그리디 알고리즘이라는 것을 생각하고 규칙을 찾으면 간단하게 풀 수 있는 문제였다. 처음에는 피보나치라고 해서 dp를 사용해야 하나 했는데.. 다시 생각해보니 그럴 필요가 전혀 없었다. 피보나치 수를 생각해보면 f(n+1) = f(n)..
https://www.acmicpc.net/problem/18921 18921번: Cost Of Subtree The first line contains a single integer $n$ ($2 \le n \le 10^5$) --- the number of vertices in the tree. Each of the following $n-1$ lines contains three integers $a_i$, $b_i$ and $v_i$ ($1 \le a_i, b_i \le n$; $a_i \ne b_i$; $1 \le v_i \le 10^9$) --- the www.acmicpc.net 일단 영어로 된 문제는 백스탭하고 보지만.. 일단 읽어보았다.. 처음에 A subtree of the tree i..
https://www.acmicpc.net/problem/2450 2450번: 모양 정돈 첫째 줄에는 모양의 전체 개수 N이 주어진다. N은 3이상 100,000이하이다. 둘째 줄에는 나열된 모양들을 나타내는 N개의 정수가 빈 칸을 사이에 두고 주어지는데, 정수 1은 세모를, 정수 2는 네모를, www.acmicpc.net 어렵다.. 세가지 모양이 있고 각 모양이 적어도 하나 이상 나타나기 때문에 가능한 순서는 3! = 6가지 경우가 있다. 따라서 이 6가지 경우를 모두 보면서 각각의 이동횟수 중 최소를 출력하면 된다. 이동횟수를 구하는 방법은 더 어려웠다.. 검색해보니 대충 이해가 될 듯 한데 명확히 왜 그게 맞는지를 설명을 못하겠다. 어렴풋이 이해가 되는 정도..? 그냥 아예 확 외워버리는 게 나을수..
https://www.acmicpc.net/problem/2457 2457번: 공주님의 정원 첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, www.acmicpc.net 3월 1일을 포함하는 날짜를 가진 꽃 중에 지는 날이 제일 먼 꽃을 선택하여 그 꽃이 지는 날을 다시 시작날짜로 놓고, 이 과정을 반복해서 시작 날짜가 11월 30일보다 커지면 ans를 출력한다. 비교를 쉽게 하기 위해 날짜를 숫자로 변환한다 ex) 3월 1일 = 301, 11월 30일 = 1130 또한 정렬을 통해 O(N)시간 안에 탐색이 가능하도록 한다. 꽃 배열을 돌다가 ..
https://www.acmicpc.net/problem/2180 2180번: 소방서의 고민 첫째 줄에 화재 발생 건수 n이 주어진다. n은 200,000 이하의 양의 정수이다. 둘째 줄부터 n개의 줄에 각각 한 줄에 한 쌍씩 a와 b가 입력된다. a와 b는 40,000 이하의 음이 아닌 정수이다. www.acmicpc.net a가 제일 큰 화재부터 먼저 진압하고, a가 같은 경우에는 b가 작은 화재부터 먼저 진압한다.. 예제도 모두 맞는데, 시간초과가 난다.... c++로 갈아탄 후에는 틀렸습니다. 가 나오는 걸로 봐서는 이렇게 풀면 안되나 보다.. 내가 c++을 잘 몰라서 틀린 걸 수도.. 아무튼 수식으로 정리를 해서 풀었다.. b/a < d/c 로 했더니 또 틀렸습니다.. 나와서 곱셈으로 바꿔서 했..
https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 현재 위치한 도시에서의 리터당 가격이 다음 도시의 리터당 가격보다 비싸면 사야하는 최소한의 양(다음 도시까지 가는 데 필요한 양) 만큼만 구입하고, 현재 위치한 도시에서의 리터당 가격이 다음 가야하는 곳 보다 싼 경우에는 현재 가격보다 더 싼 도시가 나타날때까지의 거리를 가는 데 필요한 리터만큼 구입한다. import sys input = sys.stdin.readline N = i..
https://www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 머리가 안돌아가서.. 도저히 풀 수 있는 방법이 생각나지를 않았다. 예시의 답이 1+1+2+3+6+7 = 20 보다 하나 더 큰 수라는 건 알았지만, 그리디를 이용해서 어떤 공식을 찾을 수 있을 지 생각이 나질 않았다. 그래서 질문을 좀 검색해 본 결과.. 현재 뽑은 숫자가 지금까지 더한 숫자 보다 작다면 그 수는 지금 까지의 더한 수(SUM) 부터 뽑은 수를 더한 값(SUM + ARR[i]) 까지 만들 수..
