백준 알고리즘

매우 간단한 문제이다. 입력을 받고, 연속해서 숫자를 더해나간다. 그러면 시작점부터, 그 지점까지의 합은 쉽게 구해진다. 음수값이 등장한다. 시작점부터 합을 구했을때 어떠한 구간이 음수라면,그 구간은 제외시키도록 한다. 연속합의 최대값은, 해당 지점까지의 합과 시작점부터 해당지점, 즉 그 구간 내에 있는 음수영역을 빼준 결과중 최대값이다. #include #include int main() { std::cin.tie(0); std::cin.sync_with_stdio(false); std::cout.tie(0); std::cout.sync_with_stdio(false); int MinSumUntilNow = 0; int MaxSumUntilNow = -1001; int LastSum = 0; int S..

간단한 동적계획법 문제이다. 이 문제는 아주 예전부터 백준 알고리즘에서 동적계획법으로 문제 분류가 되었다고 한다. 그 만큼 아주 괜찮은 문제라는 것... 아래의 그림을 보도록 하자. N번째 집을 R로 칠했을때의 최대값은 그 이전인 N-1을 G로 칠했을때와 B로 칠했을때의 값중 최대값을 골라서 N번째 집을 R로 칠했을 때의 비용을 합산한 것이다. 그러면 N-1 번째 집을 G 또는 B로 칠했을때의 최대값은 어떻게 구하는가? 또 N-2번째에서의 최대값을 구해봐야하고 이러면 또 N-3 또 N-4 또 N-5 쭉쭉쭉 이어져서 1번째까지 내려가게 된다. 재귀함수로 분기를 하고, 같은 계산시 이득을 볼수 있도록 배열로 저장해둔 값을 적용한다. 코드는 다음과 같다. #include #include enum RGB { R..

LIS를 이루는 것을 알아내고 나면 쉽게 풀어낼 수 있다. LIS 기본 문제는 다음을 참고하도록 하자. 2022.01.16 - [프로그래밍/알고리즘] - [BOJ 11053] 가장 긴 증가하는 부분수열 - LIS 예제의 B 전봇대를 보도록 하자. A 전봇대의 B 전봇대의 타겟을 수열로 나타내면, 8 2 9 1 4 6 7 10 이다. 수열이 증가하는 순서라면 엉키지 않는다. 따라서, 최대 증가 부분 수열을 이루는 부분을 제외하고 나머지 전깃줄을 제거하면 답을 구할수 있다. LIS의 길이를 구하고, 전깃줄의 개수에서 빼준다. #include #include #include int LineTargets[501]= { 0 , }; int main() { std::cin.tie(0); std::cout.tie(0..