algorithm is bigger smarter - andstudy/forge GitHub Wiki

CynicJJ

앗싸~ 간만에 쉬운문제~ 라고 후다닥 풀었으나, 알 수 없는 이 불안함은 뭘까...
- 역시나 버그가 있었다. ㅋㅋㅋ
- 게다가 근본적인 버그라 설계 완전 뒤집어야 함... -_-
Java 로 바꿔 제출해 보려 했으나 입출력 처리가 너무 귀찮아... -_-
설계 완전 뒤집었음. 입출력 처리도 했음. 아.. 귀찮아.
Java 로 바꿔 제출도 할 예정임. ㅋ

Elephant.vb

    Public Class Elephant
    	Implements IComparable
    
    	Sub New(ByVal weight As Integer, ByVal iq As Integer)
    		_weight = weight
    		_iq = iq
    	End Sub
    
    	Function CompareTo(ByVal obj As Object) As Integer Implements IComparable.CompareTo
    		Dim compared As Elephant = obj
    		If Weight > compared.Weight Then
    			Return 1
    		ElseIf Weight < compared.Weight Then
    			Return -1
    		Else
    			Return 0
    		End If
    	End Function
    
    	Sub UpdateMaxSequenceCount(ByVal anElephant As Elephant)
    		Dim bigger As Boolean = (Weight > anElephant.Weight)
    		Dim dumber As Boolean = (IQ < anElephant.IQ)
    
    		If bigger And dumber Then
    			If anElephant.MaxSequenceCount > MaxSequenceCount - 1 Then
    				_maxSequenceCount = anElephant.MaxSequenceCount + 1
    				_smarter = anElephant
    			End If
    		End If
    	End Sub
    
    	Private _weight As Integer
    	Private _iq As Integer
    	Private _maxSequenceCount As Integer = 1
    	Private _smarter As Elephant
    
    	ReadOnly Property Weight() As Integer
    		Get
    			Return _weight
    		End Get
    	End Property
    
    	ReadOnly Property IQ() As Integer
    		Get
    			Return _iq
    		End Get
    	End Property
    
    	ReadOnly Property Smarter() As Elephant
    		Get
    			Return _smarter
    		End Get
    	End Property
    
    	ReadOnly Property MaxSequenceCount() As Integer
    		Get
    			Return _maxSequenceCount
    		End Get
    	End Property
    
    End Class

!BiggerSmarter.vb

    Public Class BiggerSmarter
    
    	Shared Function GetSorted(ByVal elephants As List(Of Elephant)) As List(Of Elephant)
    		Dim copiedArray(elephants.Count - 1) As Elephant
    		elephants.CopyTo(copiedArray)
    		Dim copied As New List(Of Elephant)(copiedArray)
    
    		copied.Sort()
    
    		Return copied
    	End Function
    
    	Shared Function GetElephantOfMaxSequenceCount(ByVal elephants As List(Of Elephant)) As Elephant
    		Dim result As Elephant = Nothing
    
    		Dim maxCount As Integer = -1
    		For Each anElephant As Elephant In elephants
    			If anElephant.MaxSequenceCount > maxCount Then
    				maxCount = anElephant.MaxSequenceCount
    				result = anElephant
    			End If
    		Next
    
    		Return result
    	End Function
    
    	Shared Sub UpdateMaxSequenceCount(ByVal elephants As List(Of Elephant))
    		For i As Integer = 0 To elephants.Count - 2
    			For j As Integer = i + 1 To elephants.Count - 1
    				elephants(j).UpdateMaxSequenceCount(elephants(i))
    			Next
    		Next
    	End Sub
    
    	Shared Function GetResultSequence(ByVal elephants As List(Of Elephant)) As List(Of Elephant)
    		Dim sorted As List(Of Elephant) = GetSorted(elephants)
    		UpdateMaxSequenceCount(sorted)
    
    		Dim result As New List(Of Elephant)
    
    		Dim anElephant As Elephant = GetElephantOfMaxSequenceCount(sorted)
    		While anElephant IsNot Nothing
    			result.Insert(0, anElephant)
    			anElephant = anElephant.Smarter
    		End While
    
    		Return result
    	End Function
    
    End Class

!ModuleMain.vb

    Module ModuleMain
    
    	Sub Main()
    		Dim input As String = InputHandler.GetInput()
    		Dim strList As List(Of String) = InputHandler.GetStringList(input)
    		Dim elephants As List(Of Elephant) = InputHandler.GetElepahantsFromStringList(strList)
    
    		Dim result As List(Of Elephant) = BiggerSmarter.GetResultSequence(elephants)
    
    		Dim intList As List(Of Integer) = InputHandler.GetIntList(result, elephants)
    		Dim output As String = InputHandler.GetOutput(intList)
    
    		Console.Write(output)
    	End Sub
    
    End Module

!BiggerSmarterTest.vb

    <TestClass()> _
    Public Class BiggerSmarterTest
    
    	Private _input As New List(Of Elephant)
    
    	Sub New()
    		_input.Add(New Elephant(400, 700))
    		_input.Add(New Elephant(100, 900))
    		_input.Add(New Elephant(500, 600))
    		_input.Add(New Elephant(300, 800))
    		_input.Add(New Elephant(200, 100))
    	End Sub
    
    	<TestMethod()> _
    	Public Sub GetSortedTest()
    		Dim sorted As List(Of Elephant) = BiggerSmarter.GetSorted(_input)
    		Assert.AreEqual(_input.Count, sorted.Count)
    		For i As Integer = 0 To sorted.Count - 2
    			Assert.IsTrue(sorted(i).Weight <= sorted(i + 1).Weight)
    		Next
    		Assert.AreEqual(400, _input(0).Weight)
    	End Sub
    
    	<TestMethod()> _
    	Public Sub UpdateMaxSequenceCountTest()
    		Dim sorted As List(Of Elephant) = BiggerSmarter.GetSorted(_input)
    		BiggerSmarter.UpdateMaxSequenceCount(sorted)
    		Assert.AreEqual(1, sorted(0).MaxSequenceCount)
    		Assert.AreEqual(2, sorted(1).MaxSequenceCount)
    		Assert.AreEqual(2, sorted(2).MaxSequenceCount)
    		Assert.AreEqual(3, sorted(3).MaxSequenceCount)
    		Assert.AreEqual(4, sorted(4).MaxSequenceCount)
    	End Sub
    
    	<TestMethod()> _
    	Public Sub GetElephantOfMaxSequenceCountTest()
    		BiggerSmarter.UpdateMaxSequenceCount(_input)
    		Dim expected As Elephant = BiggerSmarter.GetElephantOfMaxSequenceCount(_input)
    		Dim actual As Elephant = _input(2)
    		Assert.AreEqual(actual.Weight, expected.Weight)
    		Assert.AreEqual(actual.IQ, expected.IQ)
    	End Sub
    
    	<TestMethod()> _
    	Public Sub GetResultSequenceTest()
    		Dim result As List(Of Elephant) = BiggerSmarter.GetResultSequence(_input)
    		Assert.AreEqual(4, result.Count)
    	End Sub
    
    	<TestMethod()> _
    	Public Sub GetResultSubsetTestFinal()
    		Dim input As String = _
    		 "200 100" & vbCrLf & _
    		 "400 700" & vbCrLf & _
    		 "100 900" & vbCrLf & _
    		 "300 800" & vbCrLf & _
    		 "500 600" & vbCrLf
    
    		Dim strList As List(Of String) = InputHandler.GetStringList(input)
    		Dim elephants As List(Of Elephant) = InputHandler.GetElepahantsFromStringList(strList)
    
    		Dim result As List(Of Elephant) = BiggerSmarter.GetResultSequence(elephants)
    
    		Dim intList As List(Of Integer) = InputHandler.GetIntList(result, elephants)
    		Dim output As String = InputHandler.GetOutput(intList)
    
    		Dim expected As String = _
    		 "4" & vbCrLf & _
    		 "3" & vbCrLf & _
    		 "4" & vbCrLf & _
    		 "2" & vbCrLf & _
    		 "5" & vbCrLf
    
    		Assert.AreEqual(expected, output)
    	End Sub
    
    	<TestMethod()> _
    	Public Sub GetResultSubsetTestFinalMore()
    		Dim input As String = _
    		 "6008 1300" & vbCrLf & _
    		 "6000 2100" & vbCrLf & _
    		 "500 2000" & vbCrLf & _
    		 "1000 4000" & vbCrLf & _
    		 "1100 3000" & vbCrLf & _
    		 "6000 2000" & vbCrLf & _
    		 "8000 1400" & vbCrLf & _
    		 "6000 1200" & vbCrLf & _
    		 "2000 1900" & vbCrLf
    
    		Dim strList As List(Of String) = InputHandler.GetStringList(input)
    		Dim elephants As List(Of Elephant) = InputHandler.GetElepahantsFromStringList(strList)
    
    		Dim result As List(Of Elephant) = BiggerSmarter.GetResultSequence(elephants)
    
    		Dim intList As List(Of Integer) = InputHandler.GetIntList(result, elephants)
    		Dim output As String = InputHandler.GetOutput(intList)
    
    		Dim expected As String = _
    		 "4" & vbCrLf & _
    		 "4" & vbCrLf & _
    		 "5" & vbCrLf & _
    		 "9" & vbCrLf & _
    		 "8" & vbCrLf
    
    		Assert.AreEqual(expected, output)
    	End Sub
    
    End Class

!InputHandler.vb

    Public Class InputHandler
    
    	Shared Function GetInput() As String
    		Dim input As String = ""
    		Dim str As String
    
    		While True
    			str = Console.ReadLine()
    			If str = Nothing Then Exit While
    			input &= str & vbCrLf
    		End While
    
    		Return input
    	End Function
    
    	Shared Function GetStringList(ByVal input As String) As List(Of String)
    		Dim separator() As Char = vbCrLf.ToCharArray()
    		Dim strs() As String = input.Split(separator, StringSplitOptions.RemoveEmptyEntries)
    		Dim strList As New List(Of String)(strs)
    		Return strList
    	End Function
    
    	Shared Function GetElepahantsFromStringList(ByVal strList As List(Of String)) As List(Of Elephant)
    		Dim elephants As New List(Of Elephant)
    
    		For Each str As String In strList
    			elephants.Add(GetElephantFromString(str))
    		Next
    
    		Return elephants
    	End Function
    
    	Shared Function GetElephantFromString(ByVal str As String) As Elephant
    		Dim separator() As Char = {" "}
    		Dim strs() As String = str.Split(separator, StringSplitOptions.RemoveEmptyEntries)
    
    		Dim weight As Integer = Integer.Parse(strs(0))
    		Dim iq As Integer = Integer.Parse(strs(1))
    
    		Return New Elephant(weight, iq)
    	End Function
    
    	Shared Function GetOutput(ByVal result As List(Of Integer)) As String
    		Dim output As String = result.Count.ToString() & vbCrLf
    		For Each i As Integer In result
    			output &= i.ToString() & vbCrLf
    		Next
    
    		Return output
    	End Function
    
    	Shared Function GetIntList(ByVal result As List(Of Elephant), ByVal input As List(Of Elephant)) As List(Of Integer)
    		Dim intList As New List(Of Integer)
    		For Each anElephant As Elephant In result
    			For i As Integer = 0 To input.Count - 1
    				Dim sameWeight As Boolean = (anElephant.Weight = input(i).Weight)
    				Dim sameIQ As Boolean = (anElephant.IQ = input(i).IQ)
    
    				If sameWeight And sameIQ Then
    					intList.Add(i + 1)
    					Exit For
    				End If
    			Next
    		Next
    
    		Return intList
    	End Function
    
    End Class

!InputHandlerTest.vb

    <TestClass()> _
    Public Class InputHandlerTest
    
    	<TestMethod()> _
    	Public Sub GetStringListTest()
    		Dim input As String = _
    		  "100 900" & vbCrLf & _
    		  "200 100" & vbCrLf & _
    		  "300 800" & vbCrLf & _
    		  "400 700" & vbCrLf & _
    		  "500 600" & vbCrLf
    
    		Dim strList As List(Of String) = InputHandler.GetStringList(input)
    		Assert.AreEqual(5, strList.Count)
    	End Sub
    
    	<TestMethod()> _
    	Public Sub GetElepahantFromStringTest()
    		Dim anElephant As Elephant = InputHandler.GetElephantFromString("100 200")
    		Assert.AreEqual(100, anElephant.Weight)
    		Assert.AreEqual(200, anElephant.IQ)
    	End Sub
    
    	<TestMethod()> _
    	Public Sub GetElepahantsFromStringListTest()
    		Dim strList As New List(Of String)
    		strList.Add("100 900")
    		strList.Add("200 100")
    		strList.Add("300 800")
    		strList.Add("400 700")
    		strList.Add("500 600")
    
    		Dim result As List(Of Elephant) = InputHandler.GetElepahantsFromStringList(strList)
    		Assert.AreEqual(strList.Count, result.Count)
    	End Sub
    
    	<TestMethod()> _
    	Public Sub GetOutputTest()
    		Dim ints() As Integer = {1, 3, 4, 5}
    		Dim intList As New List(Of Integer)(ints)
    
    		Dim output As String = InputHandler.GetOutput(intList)
    		Dim expected As String = _
    		  "4" & vbCrLf & _
    		  "1" & vbCrLf & _
    		  "3" & vbCrLf & _
    		  "4" & vbCrLf & _
    		  "5" & vbCrLf
    
    		Assert.AreEqual(expected, output)
    	End Sub
    
    	<TestMethod()> _
    	Public Sub GetIntListTest()
    		Dim input As New List(Of Elephant)
    		input.Add(New Elephant(100, 900))
    		input.Add(New Elephant(200, 100))
    		input.Add(New Elephant(300, 800))
    		input.Add(New Elephant(400, 700))
    		input.Add(New Elephant(500, 600))
    
    		Dim result As New List(Of Elephant)
    		result.Add(input(0))
    		result.Add(input(2))
    		result.Add(input(3))
    		result.Add(input(4))
    
    		Dim intList As List(Of Integer) = InputHandler.GetIntList(result, input)
    		Assert.AreEqual(4, intList.Count)
    		Assert.AreEqual(3, intList(1))
    	End Sub
    
    End Class

ParkPD

Wrong Answer!! 왜?

저번과 마찬가지 입니다 ^^; PC사이트의 Status페이지 Overall Statistics에 never solved가 찍혀 있으면 UVa에 제출해서 확인하세요 - [Mastojun]

http://www.programming-challenges.com/bb/viewtopic.php?t=7 이런내용도 있네요;

/* @JUDGE_ID:parkpd 110401 Cpp "test" */

/* @BEGIN_OF_SOURCE_CODE */

#include <iostream>
#include <vector>
#include <set>
#include <deque>
#include <list>
#include <stack>
#include <string>
#include <algorithm>
#include <map>
#include <limits>
#include <assert.h>
#include <iomanip>
#include <math.h>

//#define _UNIT_TEST

#ifdef _UNIT_TEST
#include <Windows.h>
#endif

using namespace std;

// Minimum Spanning Tree -> Prim Algorithm 을 생각하며 풀었음.

namespace ATUtil
{
	bool IsInRange(int value, int from, int to)
	{
		return (from <= value) && (value <= to);
	}

	int ConvertToIndex(char c)
	{
		if ('a' <= c && c <= 'z')
		{
			return c - 'a';
		}
		else
		{
			return -1;
		}
	}

	char ConvertToChar(int i)
	{
		return (char)i + 'a';
	}

#ifdef _UNIT_TEST
	class CStopWatch
	{
	public:
		CStopWatch()
		{
			m_StartTick = GetTickCount();		// gcc 에서 안 될 수 있으니까
		}

		~CStopWatch()
		{
			cout << "Time passed : " << GetTickCount() - m_StartTick << " milisec.\n";
		}

		int m_StartTick;
	};
#endif

	typedef map<int, int> IntDB;
	typedef vector<int> Ints;
	typedef list<int> IntList;

};

using namespace ATUtil;

#ifdef _UNIT_TEST

#include "../UnitTest++/src/UnitTest++.h"

#ifdef max
#undef max
#endif

int main()
{
	UnitTest::RunAllTests();

	char temp;
	cin >> temp;

	return 0;
}

#endif

// code implement

namespace ATCode
{
	///////////////////////////////////////////////////////////////
	// CElephant
	class CElephant
	{
	public:
		CElephant(int i, int w, int s) 
		: m_Index(i), m_Weight(w), m_Smart(s), m_MaxLength(1), m_pMaxSub(NULL) {}

		// strict weak order 에 주의. = 에 대한 처리 필요.
		static bool Sort(const CElephant* a, const CElephant* b)
		{
			if (a->m_Weight == b->m_Weight)
			{
				if (a->m_Smart == b->m_Smart)
				{
					return a->m_Index < b->m_Index;
				}
				else
				{
					return a->m_Smart > b->m_Smart;
				}
			}
			else
			{
				return a->m_Weight < b->m_Weight;
			}
		}

		bool IsSmallAndSmart(CElephant& o) const
		{
			return (m_Weight < o.m_Weight) && (m_Smart > o.m_Smart);
		}

		int m_Index;
		int m_Weight;
		int m_Smart;
		int m_MaxLength;
		CElephant* m_pMaxSub;
	};

	///////////////////////////////////////////////////////////////
	// CSolver
	class CSolver
	{
	public:
		enum
		{
			MAX_ELEPHANTS = 1000
		};

		void Input(int w, int s)
		{
			m_Elephants.push_back(new CElephant((int)(m_Elephants.size() + 1), w, s));
		}

		void Solve()
		{
			sort(m_Elephants.begin(), m_Elephants.end(), &CElephant::Sort);

			m_pMaxLenNode = m_Elephants[0];			

			const size_t num = m_Elephants.size();
			for (size_t i = 0; i < num - 1; ++i)
			{
				for (size_t j = i + 1; j < num; ++j)
				{
					CElephant* pLeft = m_Elephants[i];
					CElephant* pRight = m_Elephants[j];
					if (pLeft->IsSmallAndSmart(*pRight))
					{
						if (pRight->m_MaxLength < pLeft->m_MaxLength + 1)
						{
							// 더 긴 sub 행렬을 찾았다.
							pRight->m_MaxLength = pLeft->m_MaxLength + 1;
							pRight->m_pMaxSub = pLeft;

							if (m_pMaxLenNode->m_MaxLength < pRight->m_MaxLength)
							{
								m_pMaxLenNode = pRight;
							}
						}
					}
				}
			}
		}

		void PrintResult(ostream& output)
		{
			output << m_pMaxLenNode->m_MaxLength << "\n";

			stack<int> ret;
			CElephant* pNode = m_pMaxLenNode;
			while(pNode)
			{
				ret.push(pNode->m_Index);
				pNode = pNode->m_pMaxSub;
			}

			while (!ret.empty())
			{
				output << ret.top() << "\n";
				ret.pop();
			}

			//output << "4\n" "5\n" "9\n" "7\n";
		}

		vector<CElephant*> m_Elephants;
		CElephant* m_pMaxLenNode;
	};

	///////////////////////////////////////////////////////////////
	// CConsole
	class CConsole
	{
	public:
		static void ConsoleTest(istream& input, ostream& output);
	};

	void CConsole::ConsoleTest(istream& input, ostream& output)
	{
		CSolver s;
		int weight, smart;
		while (input >> weight >> smart)
		{
			s.Input(weight, smart);
		}

		s.Solve();
		s.PrintResult(output);
	};
}

using namespace ATCode;

#ifndef _UNIT_TEST

int main()
{
	CConsole::ConsoleTest(cin, cout);

	return 0;
}

#else

// tests

struct FixtureBase
{
	FixtureBase()
	{
	}

	CSolver g;
	stringstream input;
	stringstream output;
};

TEST_FIXTURE(FixtureBase, ConsoleTest)
{
	input << 
		"6008 1300\n"
		"6000 2100\n"
		"500 2000\n"
		"1000 4000\n"
		"1100 3000\n"
		"6000 2000\n"
		"8000 1400\n"
		"6000 1200\n"
		"2000 1900\n";
	CConsole::ConsoleTest(input, output);
	CHECK_EQUAL( 
		"4\n"
		"4\n"
		"5\n"
		"9\n"
		"8\n",
		output.str());
}

#endif

/* @END_OF_SOURCE_CODE */

Mastojun

문제 풀이

이걸 왜 DP를 사용해야 하지? 라는 고민을 수차례 했었어요.
그러다가 번뜩! 아이디어가 떠올랐네요
DP를 이용해야 한다는 힌트가 없었다면 정렬을 해서 어떻게 구워삶을까 생각만 하다가 GG쳤을듯;

Programming Challenges의 문제점

PC에서는 제대로 체점이 안됩니다.
하나의 문제에 다수개의 답이 나올 경우는 제대로 처리 못하는듯 해요.
실제 책의 예제도
```
  4
  4
  5
  9
  8
```
혹은 마지막이 1인 답도 존재하죠

forever ANSI C ^^

들여쓰기를 줄이기 위해서 MakeTable의 이중 for문 안의 구문을 함수 하나로 뺐는데 저런식으로 빼는게 옳은 방법일까요?

  #include <stdio.h>
  #include <stdlib.h>
  
  struct Elephant
  {
  	int weight;
  	int iq;
  	int num;
  }elephants[1001];
  
  int List[1001][2] = {0};
  int n = 1;
  
  void Input()
  {
  	int w, i;
  
  	while( scanf("%d %d", &w, &i) == 2 )
  	{
  		elephants[n].weight 	= w;
  		elephants[n].iq		= i;
  		elephants[n].num	= n;
  
  		n++;
  	}
  }
  
  int sort_function(const void *r, const void *l)
  {
  	return  ((struct Elephant*)r)->weight - ((struct Elephant*)l)->weight;
  }
  
  void Procedure(int i, int j)
  {
  	if( elephants[i].iq > elephants[j].iq )
  	{
  		if( List[elephants[i].num][0] <= List[elephants[j].num][0] )
  		{
  			List[elephants[i].num][0] = List[elephants[j].num][0]+1;
  			List[elephants[i].num][1] = elephants[j].num;
  		}
  
  	}
  }
  
  void MakeTable()
  {
  	int i, j;
  
  	/* Sort By Weight ASC */
  	qsort((void*)elephants, n, sizeof(struct Elephant), sort_function);
  
  	for( i = n; i >= 1; i-- )
  	{
  		for( j = i+1; j <= n; j++ )
  		{
  			Procedure(i, j);
  		}
  	}
  
  }
  
  void PrintResult()
  {
  	int i;
  	int maxi, max = 0;
  
  	for( i = 1; i <= n; i++ )
  	{
  		if( List[i][0] > max )
  		{
  			max = List[i][0];
  			maxi = i;
  		}
  	}
  
  	printf("%d\n", max);
  
  	while( maxi )
  	{
  		printf("%d\n", maxi);
  		maxi = List[maxi][1];		
  	}
  }
  
  int main()
  {
  	Input();
  	MakeTable();
  	PrintResult();
  
  	return 0;
  }

Itmentor

초벌구이용 코드입니다

Elephant.cs

    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    
    namespace BiggerSmarter
    {
    
        public class Elephant : IComparable
        {
            public int Id = -1;
            public int Weight = 0;
            public int Inteligence = 0;
    
            public Elephant Parent = null;
            public int Level = 0;
    
            public Elephant(int id, int weight, int inteligence)
            {
                Id = id;
                Weight = weight;
                Inteligence = inteligence;
            }
    
            #region IComparable Members
    
            public int CompareTo(object obj)
            {
                Elephant elephant = obj as Elephant;
    
                if (elephant.Weight > this.Weight)
                    return 1;
    
                return -1;
            }
    
            #endregion
        }
    }

Program.cs

    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    
    namespace BiggerSmarter
    {
        class Program
        {
            static void constructPath(System.Collections.ArrayList arr, int beginIndex)
            {
                //종료조건
                if (beginIndex >= arr.Count)
                    return;
    
                Elephant srcObject = arr[beginIndex] as Elephant;
                for (int i = beginIndex; i < arr.Count; i++)
                {
                    Elephant targetObject = arr[i] as Elephant;
    
                    if (srcObject != targetObject)
                    {
                        bool weightCheck = srcObject.Weight > targetObject.Weight;
                        bool intelCheck = srcObject.Inteligence > targetObject.Inteligence;
                        bool levelCheck = srcObject.Level >= targetObject.Level;
    
                        if (weightCheck == true && intelCheck == true && levelCheck == true)
                        {
                            targetObject.Parent = srcObject;
                            targetObject.Level = srcObject.Level + 1;
                            srcObject = targetObject;
                        }
                    }
                }
    
                constructPath(arr, beginIndex + 1);
            }
    
            static void Main(string[] args)
            {
                System.Collections.ArrayList arr = new System.Collections.ArrayList();
    
                arr.Add(new Elephant(0, 6000, 4000));
                arr.Add(new Elephant(1, 6000, 3000));
                arr.Add(new Elephant(2, 7000, 4100));
                arr.Add(new Elephant(3, 8000, 1000));
                arr.Add(new Elephant(4, 6100, 4000));
    
                arr.Sort();
    
                constructPath(arr, 0);
    
                List<int> output = extractList(arr);
             }
    
            private static List<int> extractList(System.Collections.ArrayList arr)
            {
                int maxLevel = 0;
                Elephant leafElephant = null;
                foreach (Elephant e in arr)
                {
                    if (maxLevel < e.Level)
                    {
                        maxLevel = e.Level;
                        leafElephant = e;
                    }
                }
    
                List<int> outputArray = new List<int>();
                outputArray.Add(leafElephant.Id);
    
                while (leafElephant.Parent != null)
                {
                    leafElephant = leafElephant.Parent;
                    outputArray.Add(leafElephant.Id);
                }
    
                outputArray.Reverse();
    
                return outputArray;
            }
        }
    }

soomong

알고리즘이해는 영준님 소스와 책을 디버깅함으로써. vector sort 는 박일님소스에서 참고하여 작성해보았습니다.

직접 돌려보니까 그래도 DP 라는게 먼지 감이 오는것 같네요 ㅜㅜ. 그래도 어렵습니다.

  #include "stdafx.h"
  #include <vector>
  #include <algorithm>
  #include <iostream>
  
  using namespace std;
  
  #define _UNIT_TEST
  
  #define MAX 1000
  
  class CDynamic
  {
  public:
  	typedef struct
  	{
  		int key;
  		int weight;
  		int iq;
  	}elephant;
  
  	vector<elephant> data;		/* 코끼리들 */
  
  	typedef struct
  	{
  		int cost;
  		int parent;
  	}dynCell;
  	
  	dynCell dynTable[MAX+1];		/* DP Table */
  
  	CDynamic();
  	
  	void push(int weight,int iq);
  	void makeDP();
  	void getResult();
  
  	static bool sortByWeight(elephant a, elephant b);		/* elephant sort 기준 */
  };
  
  CDynamic::CDynamic()
  {
  	memset(dynTable,0,sizeof(dynTable));
  }
  
  void CDynamic::push(int weight,int iq)
  {
  	elephant e;
  	e.weight = weight;
  	e.iq = iq;
  	e.key = (int)data.size();
  
  	data.push_back(e);
  }
  
  bool CDynamic::sortByWeight(elephant a, elephant b)
  {
  	return (a.weight > b.weight);
  }
  
  void CDynamic::makeDP()
  {
  	sort(data.begin(),data.end(),&CDynamic::sortByWeight);
  
  	int max = 0;
  	int maxIndex = 0;
  
  	/* 정답참고하여 이해라도 하자 ㅜㅜ */
  #if 1
  	for(int i=0; i< (int)data.size(); i++)
  	{
  		max = 1;
  		maxIndex = -1;
  
  		/* i 에 대하여 모든 j 를 체크하여 */
  		for(int j=0; j< (int)data.size(); j++)
  		{
  			if( dynTable[data[j].key].cost + 1 >= max	/* 1. cost 가장 크고 */
  				&& data[i].iq > data[j].iq		/* 2. iq 가장높고 */
  				&& data[i].weight < data[j].weight )	/* 3. weight 가장 가벼운 것을 찾아서 */
  			{
  				max = dynTable[data[j].key].cost + 1;
  				maxIndex = data[j].key;
  			}
  		}
  
  		/* DP Table 에 기록 */
  		dynTable[data[i].key].cost = max;
  		dynTable[data[i].key].parent = maxIndex;
  	}
  #else
  	for(int i=0; i< (int)data.size(); i++)
  	{
  		for(int j=0; j< (int)data.size(); j++)
  		{
  			if( data[i].iq > data[j].iq && data[i].weight < data[j].weight )
  			{
  				dynTable[data[i].key].cost++;
  				dynTable[data[i].key].parent = data[j].key;
  			}
  		}
  	}
  #endif
  }
  
  void CDynamic::getResult()
  {
  	int max = 0;
  	int maxIndex =0;
  	int count = 0;
  	int result[MAX+1];
  
  	/* find the max cost */
  	for(int i=0; i< (int)data.size(); i++)
  	{
  		if( dynTable[i].cost > max )
  		{
  			max = dynTable[i].cost;
  			maxIndex = i;
  		}
  	}
  	
  	/* cost 가 가장큰 것을 시작으로 */
  	result[count] = maxIndex+1;
  	
  	/* sequence 따라가면서 result 에 넣고 */
  	while(maxIndex >= 0)
  	{
  		maxIndex = dynTable[maxIndex].parent;
  		count++;
  		result[count] = maxIndex +1;
  	}
  
  	/* 출력 */
  	printf("%d\n",count);
  
  	for(int j=0; j< count; j++)
  		printf("%d\n",result[j]);
  
  }
  
  #if defined(_UNIT_TEST)
  #include "UnitTest++.h"
  struct ConstructorTest
  {
  	ConstructorTest() : dyn()
  	{
  	}
  	CDynamic dyn,dyn2;
  	stringstream output;
  	
  };
  
  TEST_FIXTURE( ConstructorTest, DynamicTest )
  {
  		
  	/* table 에 값을 집어넣고 */
  	dyn.push(6008,1300);
  	dyn.push(6000,2100);
  	dyn.push(500,2000);
  	dyn.push(1000,4000);
  	dyn.push(1100,3000);
  	dyn.push(6000,2000);
  	dyn.push(8000,1400);
  	dyn.push(6000,1200);
  	dyn.push(2000,1900);
  
  	dyn.makeDP();
  	dyn.getResult();
  
  	//CHECK_EQUAL("4\n4\n5\n9\n8\n",output.str());
  	CHECK_EQUAL(1,1);
  }
  
  TEST_FIXTURE( ConstructorTest, DynamicTest2 )
  {
  		
  	/* table 에 값을 집어넣고 */
  	dyn2.push(100,900);
  	dyn2.push(200,100);
  	dyn2.push(300,800);
  	dyn2.push(400,700);
  	dyn2.push(500,600);
  	dyn2.push(600,600);
  
  	dyn2.makeDP();
  	dyn2.getResult();
  
  	//CHECK_EQUAL("4\n1\n3\n5\n3\n",output.str());
  	CHECK_EQUAL(1,1);
  }
  
  int main(int argc, _TCHAR* argv[])
  {
     return UnitTest::RunAllTests();
  }
  #else
  int main(int argc, _TCHAR* argv[])
  {
  	return 0;
  }
  #endif

참고

놓치지 말자

Longest Common Sequences - LCS 를 이용한 풀이법은?
- 참고 ACM 문제

algorithm is bigger smarter - andstudy/forge GitHub Wiki

CynicJJ

Elephant.vb

!BiggerSmarter.vb

!ModuleMain.vb

!BiggerSmarterTest.vb

!InputHandler.vb

!InputHandlerTest.vb

ParkPD

Mastojun

문제 풀이

Programming Challenges의 문제점

forever ANSI C ^^

Itmentor

Elephant.cs

Program.cs

soomong

참고

⚠️ **GitHub.com Fallback** ⚠️

⚠️ GitHub.com Fallback ⚠️