문제 정보

백준 ( BOJ ) 1912 연속합

문제 풀이 : 그리디 알고리즘

문제 출처 : https://www.acmicpc.net/problem/1912

시작 Thinking

우선 이 문제는 두가지 풀이 방법이 있다.

dp 와 그리디 알괼즘 풀이

그러나 첨에 노트에 끄적끄적 해보는데

굳이 dp로 안하고 그리디로 풀어도 충분히 효율적인 알고리즘이라고 생각이 들어서

그리디로 풀게 되었다.

그리디 알고리즘이란?

사실 알고리즘 문제만 풀다 보면, 생소할 수 있는 알고리즘인데,

그때 그때 상황에 따라 최선의 선택을 한다는 것이다.

이건 아무래도 실전에서 쓰이는 경향이 더 크다..

(사실 나도 실전에서는 안써봤다…)

아무쪼록 그러기 위해서 배열이나 벡터를 따로 만들지 않고,

쭉 받아 냈다.

방법은 간단하다.

10 -4 3

을 보면, -4는 음수지만, 10 - 4 = 6 으로, 아직 더 커질 수 있는 가능성이 있다.

이걸 이용하는것인데,

우선 합의 결과가 양수인 경우와 음수인 경우를 나눈다.

양수라면, sum 에 더해주고, 다음꺼를 봐주면 된다.

만약 음수라면?

두가지를 고려 해 주면 된다.

temp + sum 이 음수인경우, 양수인 경우이다.

위에서 말했듯이, 양수인 경우 일단 계속 더해 나가면 된다.

물론 sum 에 temp를 더하기 전에, 최대값이 될 수 있는지 확인 해 줘야 한다.

만약에 음수라면?

sum을 0으로 초기화 시켜주면 된다.

이렇게 하면 음수만 들어올 때 문제가 될 수 있는데,

우선 모든 원소를 한번씩 최대값이 될 수 있는지 확인을 시켜 본다.

그리고, 한번이라도 양수값이 등장 했는지 확인 해 봐야 한다.

코드

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;


int main() {
	int n, temp, sum;
	priority_queue<int> pq;
	cin >> n; 
	sum =0;
	bool upTempo = false;
	for (int i = 0; i < n; i++) {
		cin >> temp; 
		pq.push(temp);
		if (temp < 0) {
			if (sum + temp > 0) {
				if (upTempo == true) {
					pq.push(sum);
					upTempo = false;
				}

				sum += temp;
			}
			else {
				if (upTempo == true) {
					pq.push(sum);
					upTempo = false;
				}
				sum = 0;
			}
		}
		else {
			sum += temp;
			upTempo = true;
		}
	}
	if (upTempo == true) {
		pq.push(sum);
		upTempo = false;
	}

	cout << pq.top();

}

후기

• 문제 풀이 소요 시간 : 23분
• 문제 난이도 : 쉬운편?