백준 1744 https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 풀이 전 나의 생각 문제를 처음 봤을 때 그냥 최대값들만 곱해서 더하면 될 것이라고 생각했는데 자세히보니 아니다. 조건을 보면 -1000 ~ 1000의 크기를 가지는 수열이기 때문에 실버 문제보다는 조금 더 생각해야 할 필요가 있다. 음수, 0, 1, 양수 이 4가지를 가지고 조건을 만들어보면 1. 양수 * 양수 2. 음수 * 음수 3. 1이 나왔을 때 4. 0이 나왔을 때 이렇게..
알고리즘 및 자료구조/그리디
백준 15903 https://www.acmicpc.net/problem/15903 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net 풀이 전 나의 생각 이 문제에서 최소값을 구하려면 단순하게 가장 최소가 되는 값들만 두 개 골라서 계속 더해주고 덮어쓰고 하면 해결된다. 하지만 최악의 수를 가정해보면 1000개의 카드, 합쳐질 횟수 15 * 1000 = 15000번, 1000000이 적힌 모든 숫자 카드 이 3가지를 계산하여 나오는 값을 과연 int로 처리할 수 있을까? 당연..
백준 1541 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 풀이 전 나의 생각 이 문제는 괄호를 적절하게 사용하여 최소값을 구하는 문제다. 예를 들어 55-50+40-30+20 이란 식이 있다고 가정하자. 최소값을 구하기 위해선 음수값을 최대로 올려야 한다. -> '-' 와 관련된 부분을 건들이면 될 것이다. 그럼 '-' 뒤에 있는 값들을 더해서 음수를 크게 만들어 보면 55 - (50 + 40) - (30 + 20) 이란 결과가 나오..
