PKU 1163. The Triangle. [판정:AC]

Solutions/Mr.K's Solution

PKU 1163. The Triangle. [판정:AC]

Milkskin 2009. 5. 15. 14:20

이건 뭐

제가 번역해놓고서 당시엔 풀이법을 모르겠어서 한쪽으로 밀어두었던 문제입니다 -_-;;

그러는 중에 들보군과 환타님의 솔루션이 올라와서 살짝 훑어보았습니다

소스는 읽다보면 풀이를 그대로 따라가게 될 것 같아서 거들떠보지도 않고 나머지 부분만 보았는데요

들보군의 것은 "AC Get"을 한글로 쳐놓은 "ㅁㅊ ㅎㄷㅅ"를 스파킹군이 이해하지 못해서 시작된 댓글놀이가 주가 되었고 -_-ㅋ

환타님의 것은 마지막에 시크하게 "그냥 큰 것만 골라서 더하면 되네요"라고 써놓은게 제 머리에 남아서 힌트가 되었습니다 -_-b

요새 계속 병원에 있어야 하는지라

"그냥 큰 것만 골라서 더하면 되네요"만 가지고 손코딩을 했습니다

크하하핰

왜 전 항상 다른 팀원들에 비해 압도적인 양의 코딩을 해야 문제가 풀리는걸까요 ㅠㅠ

#include <iostream>
#include <list>
using namespace std;

int main()
{
	int n, i, j;
	list<int> li1;
	list<int> li2;
	int temp, sum1, sum2, recall;
	list<int>::iterator iter;

scanf("%d", &n);

// input element to 1st row
	scanf("%d", &temp);
	li1.push_back(temp);

// input elements from 2nd row to nth row
	for( i = 2; i <= n; i++ )
	{
		if( i % 2 == 0 ) // i is even
		{
			li2.clear();

for( j = 1; j <= i; j++ )
			{
				sum1 = 0;
				sum2 = 0;
				scanf("%d", &temp);

if( j == 1 )
				{
					iter = li1.begin();
					sum2 = *iter;
					li1.pop_front();
					recall = sum2;
				}
				else if( j == i )
				{
					iter = li1.begin();
					sum1 = *iter;
					li1.pop_front();
					recall = sum1;
				}
				else
				{
					iter = li1.begin();
					sum1 = *iter;
					li1.pop_front();
					iter = li1.begin();
					sum2 = *iter;
					li1.pop_front();
					recall = sum2;
				}

sum1 += temp;
				sum2 += temp;

if( sum1 >= sum2 ) li2.push_back(sum1);
				else li2.push_back(sum2);

li1.push_front(recall);
			}
		}
		else // i is odd
		{
			li1.clear();

for( j = 1; j <= i; j++ )
			{
				sum1 = 0;
				sum2 = 0;
				scanf("%d", &temp);

if( j == 1 )
				{
					iter = li2.begin();
					sum2 = *iter;
					li2.pop_front();
					recall = sum2;
				}
				else if( j == i )
				{
					iter = li2.begin();
					sum1 = *iter;
					li2.pop_front();
					recall = sum1;
				}
				else
				{
					iter = li2.begin();
					sum1 = *iter;
					li2.pop_front();
					iter = li2.begin();
					sum2 = *iter;
					li2.pop_front();
					recall = sum2;
				}

sum1 += temp;
				sum2 += temp;

if( sum1 >= sum2 ) li1.push_back(sum1);
				else li1.push_back(sum2);

li2.push_front(recall);
			}
		}
	}

if( n % 2 )
	{
		li1.sort();
		iter = li1.end();
		temp = *(--iter);
		printf("%d\n", temp);
	}
	else
	{
		li2.sort();
		iter = li2.end();
		temp = *(--iter);
		printf("%d\n", temp);
	}

return 0;
}

pku에서 AC를 받고나서 들보군의 것과 환타님의 것을 다시 보니

참 개허탈합니다 ㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎ