맛있는물회

아주 간단한 그리디 알고리즘 문제이다. 문제 조건 다항식을 계산하기 위해 고안된 계산기가 있다. 이 계산기에는 0부터 9까지의 숫자와 +, ×(곱하기), x, =의 14개의 키가 있다. 예를 들어 이 계산기를 이용하여 x^3 + x + 11을 계산하려면 x, ×, x, ×, x, +, x + 1, 1, = 을 누르면 된다. 또 x^3 + 2x^2 + 11을 계산하기 위해서는 x, +, 2, ×, x, ×, x, +, 1, 1, = 을 누르면 된다. 일반적인 계산기라면 x, +, 2, ×, x, ×, x, +, 1, 1, = 을 x + 2x^2 + 11로 인식하겠지만, 이 계산기는 추가 메모리가 없기 때문에 계산을 할 때에 계산 직전에 계산기에 저장되어 있던 값에 계산을 한다. 즉 x, +, 2, ×, x..

오랜만에 다시 시작하는 알고리즘 문제라 그런지 엄청 헤맸다.... 전형적인 그리디 문제이다. 왜 처음에 접근한 방식이 안 풀린지 아직도 잘 모르겠다. 한번 더 점검해보고 다시 생각해봐야겠다. 이 문제는 먼저 Input 값이 정렬되어있다는 점에 초점을 맞추어야한다. 키가 가장 작은 "1" 부터 "N"까지 순서대로 각 자신의 왼쪽에 자신보다 키가 큰 사람의 수를 보여준다. (키가 같은 사람은 없음) 1. 틀린 접근법 처음에 생각한 방식은 "1"이 주어짐으로써 1번의 위치를 알 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 #incl..

아주 간단한 그리디 문제이다. k1과 k2로 나머지 값을 k1 = n - 2 * i k2 = m - i 이렇게 잡아주고 i를 ++해주며 반복문을 돌렸다. 만약에 if (k1

간단한 그리디 문제이다. A 문자열과 B문자열과 비교했을때 동일한 문자의 개수의 MAX값만을 구하면 된다. 예를들어 A : adaabc B: aababbc 일때 a d a a b c a a b a b b c -> 같은 문자 개수 : 3개 a d a a b c a a b a b b c -> 같은 문자 개수 : 4개 따라서 이 MAX값을 가지고 계산하면 cnt2 - MAX 가 답이다!!! 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 #define _CRT_SECURE_NO_WARNINGS #include #include int main() { char..

생각보다 시간이 꽤 오래 걸렸다......... 맨첨에 이중포문으로 O(n^2)로 계속 접근하니깐 시간초과가 계속 떴다. 0000000000000000 0000000000000000 이렇게 있으면 그냥 하나하나마다 자기 값보다 큰 값들을 비교하며 count 해서 계산했었는데 시간초과 계속 떴다. ㅠㅠ 그래서 sorting 을 사용해서 조금 더 생각하며 풀었다. 어짜피 로프에 들어가는 무게는 동일하므로 k 값을 n-i로 잡아서 하니 바로 풀렸따 .... 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51..

아주 전형적이고 간단한 그리디알고리즘 문제이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 #define _CRT_SECURE_NO_WARNINGS #include #include int main() { int n, num; int cnt = 0; int a; scanf("%d", &n); if (n 1000) return; num = 1000 - n; while (1) { if (num = 500) { a = num / 500; cnt += a; num -= a * 500; } else if (num ..

우리 동비나 형님의 말을 따라 그리디알고리즘을 마스터하기 위해 백준 그리디문제를 하루에 몇문제씩 풀 생각으로 열공하고있다. ㅎㅎ 11047번은 아주 쉬운 그리디 문제이다. 숫자도 이상하게 나와서 DP로 풀어야하는 것이 아닌 아주 전형적인 그리디알고리즘 문제! 쉽게 풀린다.!! 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 #define _CRT_SECURE_NO_WARNINGS #include #include int num; int main() { int k; int *arr; int cnt = 0; int a = 0; int i = 0; scanf("%d %d", &num, &k); arr = ..