- ์ฒ์์ ์์ฌ์์ด ๊ธฐ๋ฒ์ผ๋ก ์ ๊ทผํ๋ค๊ฐ ์คํจ!
- ์ฑ
๋ค์ชฝ ๋ณด๋ "์ฌ๊ทํจ์๋ฅผ ์ด์ฉํ ์ ์์ง ์์๊น?" ๋ผ๋ ํํธ๊ฐ ์์ด์ ์ฌ๊ท๋ก ์ ๊ทผ.
- ๋ถํ์ํ ๋ฐ๋ณต ์ฌ๊ท๋ฅผ ํผํ๊ธฐ ์ํด์ DP์ฌ์ฉ :D
#include <stdio.h>
#define ever (;;)
int l;
int n;
int position[51];
int DynamicTable[51][51];
void input()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++ )
{
scanf("%d", position+i);
}
}
int GetResult(int prelen, int len, int s, int e)
{
int min = len*50, t;
if( s == e ) return len;
if( s >= e ) return 0;
if( DynamicTable[s][e] ) return len+DynamicTable[s][e];
for( int i = s; i <= e; i++ )
{
t = GetResult( prelen, position[i] - prelen, s, i-1);
t += GetResult( position[i] , len - position[i] + prelen, i+1, e);
if( t < min )
{
min = t;
}
}
DynamicTable[s][e] = min;
return len + min;
}
void InitTable()
{
for(int i = 1; i <= n; i++ )
{
for(int j = 1; j <= n ;j++ )
{
DynamicTable[i][j] = 0;
}
}
}
int main()
{
for ever
{
scanf("%d", &l);
if( l == 0 ) break;
input();
InitTable();
printf("The minimum cutting is %d.\n", GetResult(0, l, 1, n));
}
return 0;
}
- DP์ด์ฉ ์ํ๊ณ ๋ฌธ์ ์ ํน์ฑ๊ณผ Greedy๋ฐฉ์ ์ด์ฉํด์ ํธ๋์ค.. ์ ์๋จ
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace CuttingSticks
{
class Program
{
static void Main(string[] args)
{
int[] input = { 4,5,7,8 };
int length = 10;
int totalCost = cutStick(input, 0, length);
}
private static int cutStick(int[] input, int begin, int end)
{
float length = end - begin;
float pivot = (float)(end + begin) / 2;
int cutValue = getClosestInputValue(pivot, input, begin, end);
if (cutValue != 0)
{
int cost = end - begin;
System.Diagnostics.Trace.WriteLine("Cut: " + begin.ToString() + "-" + cutValue + ", " + cutValue + "-" + end.ToString() + " : " + cost.ToString());
cost += cutStick(input, begin, cutValue);
cost += cutStick(input, cutValue, end);
return cost;
}
return 0;
}
private static int getClosestInputValue(float pivot, int[] input, int begin, int end)
{
float minABS = 10000.0f;
int selectedIndex = -1;
for (int i = 0; i < input.Length; i++)
{
float diff = Math.Abs(input[i] - pivot);
if (diff < minABS && begin <= input[i] && input[i] <= end )
{
selectedIndex = i;
minABS = diff;
}
}
if (selectedIndex != -1)
{
int retVal = input[selectedIndex];
input[selectedIndex] = 0;
return retVal;
}
return 0;
}
}
}
- DP๊ฐ ๋๋์ฒด ๋ญ๊น?
- ๋ถ๋ฅดํธ ํฌ์ค~
- ๋๋ฆฌ๋ค. ์๋ฅด๋ ์์น๊ฐ ์ต๋ 50๊ณณ์ธ๋ฐ 9๊ฐ ์ ๋๊ฐ ํ๊ณ.
- ์ด์ํ ์์ด๋์ด๊ฐ ๋ ์ฌ๋ผ ๋ณ ์ง๋์ ๋ค ํด๋ดค์ผ๋ ๋ชจ๋ ์คํจ. ใ
Public Class Stick
Shared Function GetCost(ByVal length As Integer, ByVal cutPositions As List(Of Integer)) As Integer
If cutPositions.Count = 0 Then Return 0
If cutPositions.Count = 1 Then Return length
Dim leftLenth As Integer = cutPositions(0)
Dim rightLenth As Integer = length - leftLenth
Dim left As New List(Of Integer)
Dim right As New List(Of Integer)
For i As Integer = 1 To cutPositions.Count - 1
Dim pos As Integer = cutPositions(i)
If pos > leftLenth Then
right.Add(pos - leftLenth)
Else
left.Add(pos)
End If
Next
Return length + GetCost(leftLenth, left) + GetCost(rightLenth, right)
End Function
Shared Function GetMinCost(ByVal length As Integer, ByVal cutPositions() As Integer) As Integer
Dim minCost As Integer = Integer.MaxValue
Dim every As List(Of List(Of Integer)) = GetEveryPossible(length, cutPositions)
For Each posList As List(Of Integer) In every
If posList.Count = cutPositions.Length Then
Dim cost As Integer = Stick.GetCost(length, posList)
If cost < minCost Then minCost = cost
End If
Next
Return minCost
End Function
Shared Function GetEveryPossible(ByVal length As Integer, ByVal cutPositions() As Integer) As List(Of List(Of Integer))
Dim every As New List(Of List(Of Integer))
For Each pos As Integer In cutPositions
Dim aList As New List(Of Integer)
aList.Add(pos)
every.Add(aList)
Next
For i As Integer = 0 To cutPositions.Length - 1
For k As Integer = 0 To every.Count - 1
Dim aList As List(Of Integer) = every(k)
If aList.Contains(cutPositions(i)) Then Continue For
If aList.Count < i Then Continue For
For j As Integer = 1 To aList.Count
Dim subList As New List(Of Integer)(aList)
subList.Insert(j, cutPositions(i))
every.Add(subList)
Next
Next
Next
'Dim m As Integer = 0
'While m < every.Count
' If every(m).Count <> cutPositions.Length Then
' every.RemoveAt(m)
' Else
' m += 1
' End If
'End While
Return every
End Function
End Class
<TestClass()> _
Public Class StickTest
<TestMethod()> _
Public Sub GetEveryPossibleTest()
Dim cutPositions() As Integer = {2, 4, 7}
Dim every As List(Of List(Of Integer)) = Stick.GetEveryPossible(10, cutPositions)
Dim m As Integer = 0
While m < every.Count
If every(m).Count <> cutPositions.Length Then
every.RemoveAt(m)
Else
m += 1
End If
End While
Assert.AreEqual(3 * 2, every.Count)
End Sub
<TestMethod()> _
Public Sub GetMinCostTest()
Dim cutPositions1() As Integer = {2, 4, 7}
Assert.AreEqual(20, Stick.GetMinCost(10, cutPositions1))
Dim cutPositions2() As Integer = {25, 50, 75}
Assert.AreEqual(200, Stick.GetMinCost(100, cutPositions2))
Dim cutPositions3() As Integer = {4, 5, 7, 8}
Assert.AreEqual(22, Stick.GetMinCost(10, cutPositions3))
End Sub
<TestMethod()> _
Public Sub GetMinCostTestFinal()
Dim input As String = _
"100" & vbCrLf & _
"3" & vbCrLf & _
"25 50 75" & vbCrLf & _
"10" & vbCrLf & _
"3" & vbCrLf & _
"2 4 7" & vbCrLf & _
"10" & vbCrLf & _
"4" & vbCrLf & _
"4 5 7 8" & vbCrLf
Dim strList As List(Of String) = InputHandler.GetStringList(input)
Dim minCosts As New List(Of Integer)
For i As Integer = 0 To strList.Count - 1 Step 3
Dim length As Integer = Integer.Parse(strList(i))
Dim cutPositions() As Integer = InputHandler.GetCutPositios(strList(i + 2))
minCosts.Add(Stick.GetMinCost(length, cutPositions))
Next
Dim output As String = InputHandler.GetOutput(minCosts)
Dim expected As String = _
"The minimum cutting is 200." & vbCrLf & _
"The minimum cutting is 20." & vbCrLf & _
"The minimum cutting is 22." & vbCrLf
Assert.AreEqual(expected, output)
End Sub
<TestMethod()> _
Public Sub GetMinCostTestBigCase()
' ์๊ฐ์ด ์ผ๋ง๋ ๊ฑธ๋ฆฌ๋ ํ
์คํธ
Dim cutPositions(7) As Integer
For i As Integer = 0 To cutPositions.Length - 1
cutPositions(i) = i * 3 + 1
Next
Stick.GetMinCost(999, cutPositions)
End Sub
End Class
Module ModuleMain
Sub Main()
Dim input As String = InputHandler.GetInput()
Dim strList As List(Of String) = InputHandler.GetStringList(input)
Dim minCosts As New List(Of Integer)
For i As Integer = 0 To strList.Count - 1 Step 3
Dim length As Integer = Integer.Parse(strList(i))
Dim cutPositions() As Integer = InputHandler.GetCutPositios(strList(i + 2))
minCosts.Add(Stick.GetMinCost(length, cutPositions))
Next
Dim output As String = InputHandler.GetOutput(minCosts)
Console.Write(output)
End Sub
End Module
Public Class InputHandler
Shared Function GetInput() As String
Dim input As String = ""
Dim str As String
While True
str = Console.ReadLine()
If str = "0" 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 GetCutPositios(ByVal str As String) As Integer()
Dim separator() As Char = {" "}
Dim strs() As String = str.Split(separator, StringSplitOptions.RemoveEmptyEntries)
Dim cutPositions(strs.Length - 1) As Integer
For i As Integer = 0 To strs.Length - 1
cutPositions(i) = Integer.Parse(strs(i))
Next
Return cutPositions
End Function
Shared Function GetOutput(ByVal minCosts As List(Of Integer)) As String
Dim output As String = ""
For Each cost As Integer In minCosts
output &= "The minimum cutting is " & cost.ToString() & "." & vbCrLf
Next
Return output
End Function
End Class