[boj][c++] 1932 정수삼각형, 1149 RGB거리

1932 정수 삼각형

문제 보자마자 dp문제인가 싶었다. 어떤 느낌인지 감은 잡히는데 확신이 안서서 문제 분류를 봤는데 dp였다.

점화식을 세우기 위해 몇가지 로직을 생각했다. 이전항과 연관되는 부분을 찾았는데,

• 현재 항을 기준으로 왼쪽 위 혹은 오른쪽 위의 항과 현재 항의 값을 더한다.
• 그러므로 둘 중 큰 값을 현재 항에 더하면 된다.
• 다만, 단순히 숫자가 큰 것이 아니라 누적된 값이 큰 쪽을 더해야 정확한 값이 나온다.

이를 정확한 식으로 세우면 dp[i][j]=max(dp[i-1][j-1], dp[i-1][j])+graph[i][j] 로 볼 수 있다. 히히

2차원배열도 sort로 정렬할 수 있을 것 같은데 자꾸 오류가 나서 실패했다. 결국 반복문 두개 돌리는 비효율적인 방법으로 작성했는데, 2차원배열은 sort함수 적용이 안된다고 한다. sort함수를 사용하려면 pair자료형을 사용한 vector를 사용해야 한다고 한다. 이미 2차원배열을 사용했기 때문에 이 방법은 포기했다.

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

int n,ans;
int graph[501][501];
int dp[501][501];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            cin>>graph[i][j];
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+graph[i][j];
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            if(dp[i][j]>ans)
                ans=dp[i][j];
        }
    }
    cout<<ans<<endl;
}

1149 RGB거리

이것도 dp문제
처음에는 자료를 다 받고 거리를 재면 되나 싶었는데, 중간중간 가능한 경우의 수를 저장해두면 됐다. 블로그 참조함.

• 처음 거리를 받으면 현재 행이 R일 때 이전 행이 G,B인 경우
• 현재 행이 G일 때 이전 행이 R,B인 경우
• 현재 행이 B일 때 이전 행이 R,G인 경우

이렇게 세가지를 구하고 가장 마지막항의 RGB 중 값이 적은 것을 출력하면 된다. 점화식으로 표현하면

	dp[i][0]=min(dp[i-1][1],dp[i-1][2])+arr[i][0];
    dp[i][1]=min(dp[i-1][0],dp[i-1][2])+arr[i][1];
    dp[i][2]=min(dp[i-1][0],dp[i-1][1])+arr[i][2];

처음에는 일차원 배열로 문제에 접근하려고 생각했기 때문에 이런 아이디어를 생각하지 못했다. 응용 가능성이 많은 주제라 스스로 생각하는 것이 중요한데 아쉽다. 쩝!

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

int n;
int dp[1001][3];
int arr[1001][3];

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>arr[i][0]>>arr[i][1]>>arr[i][2];
        dp[i][0]=min(dp[i-1][1],dp[i-1][2])+arr[i][0];
        dp[i][1]=min(dp[i-1][0],dp[i-1][2])+arr[i][1];
        dp[i][2]=min(dp[i-1][0],dp[i-1][1])+arr[i][2];
    }
    cout<<min(dp[n][0],min(dp[n][1],dp[n][2]))<<endl;
}

승급

후후후 승급했다.