pinevienna blog

입력된 식에 적절히 괄호를 삽입하며 최솟값을 만드는 문제 최솟값을 만드려면 뺄셈 연산자 뒤에 오는 수가 크면 클수록 좋다 55-50+40=45 지만 최솟값을 만드려고 괄호를 넣는다면 55-(50+40)이 된다 (55-90 == 55-50-40) 이므로 뺄셈 연산자가 한 번 나오면 그 뒤에 수들은 계속 빼면 된다 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 #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); string str, temp; int res = 0; bool mi = false; ..

한 대의 ATM 앞에 n명의 사람이 기다리고 있다 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우 (i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분) [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다 이렇게 3, 4, 5번 까지 돈을 뽑으면 총 39분이 걸리는데, 줄 서는 순서를 잘 바꾸면 대기시간이 시간이 줄어든다 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 문제! 줄을 [2, 5, 1, 4, 3] 순서로 줄을 서면 가장 빠르게 모든 사람이 인출할 수 있는데 이 순서는 인출할 때 걸리는 시간이 짧은..

하나의 회의실에 최대 몇 개의 회의가 진행될 수 있는지 구하는 문제 왼쪽 열은 회의 시작시간, 오른쪽 열은 회의가 끝나는 시간이다 (첫 번째 줄 제외) 회의실이 하나이기 때문에 두 개의 회의가 동시에 진행될 수 없고, 한 회의가 끝난 동시에 다른 회의를 시작할 수 있다 가장 일찍 시작해서 가장 늦게 끝나는 경우도 있기 때문에 시작시간을 기준으로 삼으면 복잡해진다 가장 일찍 끝나는 회의를 기준으로 알고리즘을 시작해야한다 이런 생각을 한다면 자연스럽게 끝나는 시간을 기준으로 값을 정렬할 것이다.. 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 #include #incl..

동전을 적절히 더하여 K로 만들 때 필요한 동전 개수의 최솟값을 구하는 문제 1원 ~ 50000원 동전을 적절히 더해서 4200을 만들면 되는데, 최소한의 동전만 써야 한다 1원짜리 4200개, 5원짜리 840개, 10원짜리 420개 ··· 당연히 액수가 큰 동전을 많이 쓸수록 동전의 개수가 적어진다 내림차순으로 계산하면 50000 X, 10000 X, 5000 X, 1000원짜리 4개, 500 X, 100원짜리 2개 총 6개의 동전으로 4200을 만들 수 있다 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 #include #include using namespace std; int main(void) { ios_base::sync_..

길이가 WxH인 직사각형을 1x1씩 조각내서 WxH개의 정사각형으로 만드려고 했으나, 꼭짓점 2개를 잇는 방향으로 잘렸다 이때 잘리지 않고 멀쩡한 1x1 크기의 정사각형의 개수를 반환하는 문제 WxH에서 잘린 사각형의 개수를 빼면 된다 W+H에서 W와 H의 최대공약수를 뺀 값이 잘린 사각형의 개수다 호제씨를 불러 최대공약수를 구하고, W+H에서 빼면 된다.. 1 2 3 4 5 6 7 8 9 10 11 12 using namespace std; long gcd(long a, long b) { if (b == 0) return a; return gcd(b, a % b); } long long solution(int w, int h) { long W = w; long H = h; return W * H - (..