그리디2 [알고리즘] 수 묶기 (백준 1744번) 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 그리디하게 풀 수 있는 문제이다. 수를 정렬했을 때 양수 기준으로 가장 큰 수부터 곱해나간다. 단, 1과 쌍이 지어지는 경우는 그냥 더하는게 더 수가 크기 때문에 항상 list[i] * list[i+1]와 list[i] + list[i+1] 중 어떤게 더 큰지 비교해가면서 더한다. 음수는 반대로 가장 작은 수부터 곱해야지 가장 큰 값이 나온다. EX) (-5 * -1 = 5) > (-4 * -1 = 4) Solution import java.io.Buffere.. 2020. 10. 22. [알고리즘] 단어 수학 (백준 1339번) 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 나올 수 있는 알파벳 종류가 10가지이므로 백트랙킹으로 모든 순열을 구해도 된다. 순열을 구할 때 허용되는 최대 시간복잡도가 10!인데 알파벳이 딱 10가지이기 때문이다. 하지만 수학 수식을 활용해서 그리디 하게 풀면 훨씬 쉽게 풀 수 있다. Solution 'ABC', 'BCD' 라는 문자가 있다고 가정해보겠다. 이 두가지 문자를 수학 수식으로 나타내면 'ABC' : 100A + 10B + 1C 'BCD' : 100B + 10C + 1D 로 표현된다. 그.. 2020. 10. 21. 이전 1 다음
