욕심쟁이 판다

출처 : https://www.acmicpc.net/problem/1937

n*n의 크기의 대나무 숲이 있다. 그리고 각 지역마다 대나무의 양이 다르다. 그런데 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다. 만약에 그런 지점이 없으면 이 판다는 불만을 가지고 단식 투쟁을 하다가 죽게 된다(-_-)

이 판다의 사육사는 이런 판다를 대나무 숲에 풀어 놓아야 하는데, 어떤 지점에 처음에 풀어 놓아야 하고, 어떤 곳으로 이동을 시켜야 둘 다 소중한 생명이지만 판다가 최대한 오래 살 수 있는지 고민에 빠져 있다. 우리의 임무는 이 사육사를 도와주는 것이다. n*n 크기의 대나무 숲이 주어져 있을 때, 이 판다가 최대한 오래 살려면 어떤 경로를 통하여 움직여야 하는지 구하여라.

입력

첫째 줄에 대나무 숲의 크기 n(1<=n<=500)이 주어진다. 그리고 둘째 줄부터 1+n번째 줄 까지 대나무 숲의 정보가 주어진다. 대나무 숲의 정보는 공백을 사이로 두고 각 지역의 대나무의 양이 정수 값으로 주어진다.

출력

첫째 줄에는 판다가 최대한 살 수 있는 일수(K)를 출력한다.

예제 입력

4
14 9 12 10
1 11 5 4
7 15 2 13
6 3 16 8

예제 출력

4
다이나믹 프로그래밍 최장 증가 부분열(LIS)
대나무를 먹는 시간이 없네요. 한 곳에 있는 대나무를 다 먹는 데 대나무 양에 상관없이 하루가 걸린다... 라고 생각하면 되겠죠? - Noname, 2017/08/20 22:18 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

16개의 풀이가 있습니다. 1 / 2 Page

어떠한 수열이 주어졌을때 이 수열의 최장 증가 부분열을 찾는것은 다이나믹 프로그래밍으로 해결할 수 있는 유명한 문제입니다.

참고자료 http://dyngina.tistory.com/16

이 문제는 2차원 배열에 대해서 최장 증가 부분열 알고리즘을 적용하면 됩니다. 모든 n*n점 (i,j)에 대해서 판다의 시작점을 정해준뒤에 dfs로 탐색하면서 얻을 수 있는 가장 긴 증가하는 수열의 길이를 얻으면 됩니다.

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

int forest[501][501];  
int dp[501][501]; 
int dy[4] = {1,0,-1,0}; 
int dx[4] = {0,1,0,-1};  
int n; 

bool inRange(int y,int x){
    return (y >= 0 && y < n && x >= 0 && x < n); 
}

int find(int y,int x){
    if (dp[y][x] == 0){
        dp[y][x] = 1; 
        for (int i = 0; i < 4; i++){
            int ny = y+dy[i], nx = x+dx[i];  
            if (inRange(ny,nx) && forest[ny][nx] > forest[y][x]){
                dp[y][x] = max(dp[y][x],find(ny,nx)+1); 
            }
        }
    }
    return dp[y][x];  
}

int main(){
    scanf("%d",&n);  
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            scanf("%d",&forest[i][j]);  
        }
    }
    // dp 테이블 채우기  
    int res = 0;  
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){ // 팬더의 시작좌표를 정해주고 최댓값을 갱신한다.  
            res = max(res,find(i,j));  
        }
    }
    printf("%d\n",res);  
    return 0; 
}
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

Ruby

def max_trail(bamboos, n=[*0...bamboos.size])
  trees = n.product(n).map {|x,y| [y,x,bamboos[x][y]] }
  nexts = ->x,y,v { trees.select {|ex,ey,ev| (ex-x).abs+(ey-y).abs <2 && ev>v} }
  trail = ->t,max=0 { t[0] ? trail[t.flat_map{|e|nexts[*e]}, max+1] : max }
  trail[trees]
end

Test

bamboos_1 = [ [0, 0],
              [0, 0] ]
expect(max_trail(bamboos_1)).to eq 1

bamboos_2 = [ [ 1, 6, 7],
              [ 2, 5, 8],
              [ 3, 4, 9] ] 
expect(max_trail(bamboos_2)).to eq 9 

bamboos_3 = [ [14, 9,12,10],
              [ 1,11, 5, 4],
              [ 7,15, 2,13],
              [ 6, 3,16, 8] ]            
expect(max_trail(bamboos_3)).to eq 4
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
from multiprocessing import Pool
from random import randint
import os, sys

c = os.cpu_count()
sys.setrecursionlimit(2**13)

data = list(list(int(i) for i in j.split())for j in '''14 9 12 10
1 11 5 4
7 15 2 13
6 3 16 8'''.split('\n'))


#N = 52
#data = list(list(randint(1, 100) for i in range(N)) for j in range(N))

class block(object):
    def __init__(self, N):
        self.N = N; self.l, self.r, self.u, self.d = [None]*4
    def move_lower(self):
        return list((x for x in (self.u, self.d, self.l, self.r) if x != None and x.N < self.N))
    def move_lower_chain(self, res = [], history = []):
        return (lambda temp: (res.append(history + [self.N]) if len(temp) == 0 else list(x.move_lower_chain(res, history + [x.N]) for x in temp), res)[1])(self.move_lower())

def setmap(li):
    res, n = [], len(li)
    for j in range(n):
        res.append([])
        for i in range(n):
            res[j].append(block(li[j][i]))
            if i > 0: res[j][i-1].r, res[j][i].l = res[j][i], res[j][i-1]
            if j > 0: res[j-1][i].d, res[j][i].u = res[j][i], res[j-1][i]
    temp, res = res[:], []
    return sorted((lambda temp, res: (list(list((res.append(i)) for i in j) for j in temp), res)[1])(temp, res), key = lambda x: x.N)[::-1]
def proc(m, number, cores):
    res = []
    for i in range(number, len(m), cores):
        res.append(max(map(len, m[i].move_lower_chain())))
        if max(res) > len(m)-(i+1): break
    return res
def check(m):
    with Pool() as p:
        temp = p.starmap(proc, ((m, number, c) for number in range(c)))
    return max((lambda res: (list(list(res.append(y) for y in x) for x in temp), res)[1])([]))

if __name__ == '__main__':
    m = setmap(data)
    print(check(m))

재귀함수 제한 늘려도 52가 한계네요. 52 기준 1초 미만으로 나옵니다. 파이썬 3.5.1

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

C 언어 입니다. 입력받은 배열 N x N 과 가장긴거리를가지는 값을 가질 배열 N x N 배열의 크기를 넘어가지 않으면서 현재의 (j, i) 보다 큰값을 찾아나가면서 1씩 증가시켜줍니다. LIS를 을 만족시키고싶었는데 재귀형식으로 된거같네요 DP도 만족시키고싶어서 최대거리를 미리 구해놨으면 그쪽방향은 배열의 값을 바로 읽게했습니다. 코드길이를 줄이면서 간단하게 하고싶은데 요령이 없네요. ㅡ.ㅜ 앞으로 더 잘하겠습니당

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<malloc.h>


int isPath(int **a, int i, int j)
{
    if (i == -1 || j == -1 || i == 4 || j == 4)
        return 0;

    return a[i][j];
}
int max(int a, int b, int c, int d)
{
    int max = a;
    if (max < b)
        max = b;
    if (max < c)
        max = c;
    if (max < d)
        max = d;
    return max;
}
int initial(int **a, int **l, int j, int i)
{   
    int left = 0, right = 0, up = 0, down = 0;
    if (a[j][i] < isPath(a, j , i + 1))
    {
        if (l[j][i + 1] == 0)
            right = initial(a, l, j, i + 1);
        else
            right = l[j][i + 1];
    }
    if (a[j][i] < isPath(a, j , i -1))
    {
        if (l[j][i - 1] == 0)
            left = initial(a, l, j , i -1);
        else
            left = l[j][i - 1];
    }
    if (a[j][i] < isPath(a, j + 1, i))
    {
        if (l[j + 1][i] == 0)
            down = initial(a, l, j + 1, i);
        else
            down = l[j + 1][i];
    }
    if (a[j][i] < isPath(a, j - 1, i))
    {
        if (l[j - 1][i] == 0)
            up = initial(a, l, j - 1, i);
        else
            up = l[j - 1][i];
    }

    return 1 + max(left, right, up, down);
}

int main()
{
    int n = 0;

    scanf("%d", &n);

    int **a;
    a = (int **)malloc(sizeof(int*) * n);
    for (int i = 0; i < n; i++)
        a[i] = (int*)malloc(sizeof(int) * n);

    for (int j = 0; j < n; j++)
        for (int i = 0; i < n; i++)
            scanf("%d", &a[i][j]);


    int** LIS = (int**)malloc(sizeof(int*) * n);
    for (int i = 0; i < n; i++)
        LIS[i] = (int*)malloc(sizeof(int) * n);

    for (int j = 0; j < n; j++)
        for (int i = 0; i < n; i++)
            LIS[j][i] = 0;
    for (int j = 0; j < n; j++)
    {
        for (int i = 0; i < n; i++)
        {
            LIS[j][i] = initial(a, LIS, j, i);
        }
    }

    for (int j = 0; j < n; j++)
    {
        for (int i = 0; i < n; i++)
            printf("%d ", LIS[j][i]);
        printf("\n");
    }


}
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

Delphi 2010 DP(Dynamic Program방식) 사용

type
  TArrayInt2d = array of array of Integer;

function fnGeedyPanda(const M: TArrayInt2d; RCnt, CCnt: Integer; var ci, cj: Integer): Integer;
var
  V: array of array of Integer;
  CMax, i, j: Integer;

  function fnSearchValue(A, b, minVal: Integer): Integer;
  var
    val: Integer;
  begin
    if (A < 0) or (A = RCnt) or (b < 0) or (b = CCnt) then
      exit(0);

    if V[i, j] <> -1 then
     exit(V[i, j]);
    val := M[A, b];
    if val <= minVal then
      exit(0);
    result := 1 + Max(Max(fnSearchValue(A - 1, b, val), fnSearchValue(A + 1, b, val)),
      Max(fnSearchValue(A, b - 1, val), fnSearchValue(A, b + 1, val)));
  end;

begin
  SetLength(V, RCnt, CCnt);
  for i := 0 to RCnt - 1 do
    for j := 0 to CCnt - 1 do
      V[i, j] := -1; // 초기값이 -1 
  CMax := 0;
  ci := 0;
  cj := 0;
  for i := 0 to RCnt - 1 do
    for j := 0 to CCnt - 1 do
      if V[i, j] = -1 then
      begin
        V[i, j] := fnSearchValue(i, j, -1);
        if CMax < V[i, j] then
        begin
          ci := i;
          cj := j;
          CMax := V[i, j];
        end;
      end;
  result := CMax;
end;

procedure TForm4.btn욕심쟁이판다Click(Sender: TObject);
Const
  C: array [0 .. 3, 0 .. 3] of Integer = ((14, 9, 12, 10), (1, 11, 5, 4), (7, 15, 2, 13), (6, 3, 16, 8));
var
  ci, cj, CMax: Integer;
  M: TArrayInt2d;
begin
  // Dreedy 방식
  SetLength(M, 4, 4);
  for ci := 0 to 3 do
    for cj := 0 to 3 do
      M[ci, cj] := C[ci, cj];

  CMax := fnGeedyPanda(M, 4, 4, ci, cj);
  Memo1.Lines.Add(format('욕심쟁이 판다: Pos %d (%d,%d), Count: %d', [M[ci, cj], ci + 1, cj + 1, CMax]));
end;
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

부족한 점이 많아서 다른분보다 코드가 길은거 같아여 test

0 0

0 0

1

1 6 7

2 5 8

3 4 9

9

14 9 12 10

1 11 5 4

7 15 2 13

6 3 16 8

4

#include <stdlib.h>
#include<stdio.h>


int getMax(int t1, int t2);
int LIS(int** f, int** k, int n, int x, int y);

void main(void) {

    int n =  0;

    scanf("%d",&n);

    int** f = (int**)malloc(sizeof(int*) * n );
    for(int i = 0; i<n ; i++) {
         f[i] = (int*)malloc(sizeof(int) * n );
    }

    for(int i = 0; i<n ; i++)
        for(int j= 0; j<n ; j++) 
            scanf("%d",&f[i][j]);


    int** k = (int**)malloc(sizeof(int*) * n );
    for(int i = 0; i<n ; i++) {
         k[i] = (int*)malloc(sizeof(int) * n );
    }
    for(int i = 0; i<n ; i++)
        for(int j= 0; j<n ; j++) 
            k[i][j] = 1;
    int max = 0;
    for(int i = 0; i<n ; i++)
        for(int j= 0; j<n ; j++) 
            max = getMax(max, LIS(f, k, n, i, j));

    printf("%d\t", max);
}

int getMax(int t1, int t2) {
    if(t1 > t2)
        return t1;
    else
        return t2;
}

int LIS(int** f, int** k, int n, int x, int y) {

    for(int i = 0; i<n ; i++) {
        for(int j= 0; j<n ; j++) {
            if(f[i][j] >= f[x][y]) {
            if(i+1 < n && f[i][j] < f[i+1][j])
                k[i+1][j] = k[i][j] + 1;
            if(j+1 < n && f[i][j] < f[i][j+1])
                k[i][j+1] = k[i][j] + 1;
            if(i-1 >= 0 && f[i][j] < f[i-1][j])
                k[i-1][j] = k[i][j] + 1;
            if(j-1 >= 0 && f[i][j] < f[i][j-1])
                k[i][j-1] = k[i][j] + 1;
            }
        }
    }

    int max = 0;
    for(int i = 0; i<n ; i++) {
        for(int j= 0; j<n ; j++) {
            if(f[i][j] >= f[x][y]) {
            if(i+1 < n && f[i][j] > f[i+1][j])
                max = getMax(max ,k[i+1][j]);
            if(j+1 < n && f[i][j] > f[i][j+1])
                max = getMax(max ,k[i][j+1]);
            if(i-1 >= 0 && f[i][j] > f[i-1][j])
                max = getMax(max ,k[i-1][j]);
            if(j-1 >= 0 && f[i][j] > f[i][j-1])
                max = getMax(max ,k[i][j-1]);
            }
            k[i][j]= max + 1;
            max = 0;
        }
    }

    for(int i = 0; i<n ; i++) {
        for(int j= 0; j<n ; j++) {
            max = getMax(max ,k[i][j]);
        }
    }
    return max;
}
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

자바입니다

package study;

import java.util.Scanner;

public class panda {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int fr[][] = new int[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                fr[i][j] = sc.nextInt();
            }
        }

        int temp, answer = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                temp = solve(n, i, j, fr);
                if (answer < temp) {
                    answer = temp;
                }
            }
        }

        System.out.println(answer);

    }

    public static int solve(int n, int x, int y, int fr[][]) {
        int result = 1;
        int dir[] = { 0, 0, 0, 0 };
        if (x > 0 && fr[x][y] < fr[x - 1][y]) {
            dir[0] = solve(n, x - 1, y, fr) + 1;
        }
        if (y > 0 && fr[x][y] < fr[x][y - 1]) {
            dir[1] = solve(n, x, y - 1, fr) + 1;
        }
        if (x + 1 < n && fr[x][y] < fr[x + 1][y]) {
            dir[2] = solve(n, x + 1, y, fr) + 1;
        }
        if (y + 1 < n && fr[x][y] < fr[x][y + 1]) {
            dir[3] = solve(n, x, y + 1, fr) + 1;
        }

        for (int i = 0; i < 4; i++) {
            if (result < dir[i]) {
                result = dir[i];
            }
        }

        return result;
    }
}

어떻게 하면 더 깔끔하게 할 수 있을거 같은데 그냥 마무리

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

대나무 덕후 욕심쟁이 판다 색히

#include <stdio.h>
#define SIZE 4

enum { ROOT, L, R, T, B };

int maxDepth = 0;

void next(int a[SIZE][SIZE], int row, int col, int preDir, int preVal, int preDepth) {
    int curVal = a[row][col];
    int cond = 0;
    cond = cond || row < 0;
    cond = cond || col < 0;
    cond = cond || row > SIZE - 1;
    cond = cond || col > SIZE - 1;
    cond = cond || (preDir != ROOT && preVal >= curVal);
    if(cond) {
        if(preDepth > maxDepth)
            maxDepth = preDepth;
        return; 
    }

    int curDepth = preDepth + 1;    
    if(preDir != R) next(a, row    , col - 1, L, curVal, curDepth);
    if(preDir != L) next(a, row    , col + 1, R, curVal, curDepth);
    if(preDir != B) next(a, row - 1, col    , T, curVal, curDepth);
    if(preDir != T) next(a, row + 1, col    , B, curVal, curDepth);
}

int main() {
    int a[SIZE][SIZE] = {
                    { 14,  9, 12, 10 }, 
                    {  1, 11,  5,  4 },
                    {  7, 15,  2, 13 },
                    {  6,  3, 16,  8 }
                };

    for(int row = 0; row < SIZE; row++) {
        for(int col = 0; col < SIZE; col++) {
            next(a, row, col, ROOT, a[row][col], 0);
        }
    }
    printf("maxDepth: %d", maxDepth);   
    return 0;
}

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

자바입니다. 간단하게 작성하려고했는데 생각보다 길게 작성이됬네요.

public class GreedyPanda {
    private int[][] forest;
    private int size;
    private int MAX;

    private final int[] X = { 0, 1, 0, -1 };
    private final int[] Y = { 1, 0, -1, 0 };

    public GreedyPanda(int size, int[][] forest) {
        this.size = size;
        this.MAX = size * size;
        this.forest = forest;
    }

    public int getMaximumAliveDay() {
        int result = 0;
        int temp = 0;
        for (int i = 0; i < this.size; i++) {
            for (int j = 0; j < this.size; j++) {
                temp = findMaximumPath(i, j);
                result = temp > result ? temp : result;
                if (result == this.MAX) {
                    return result;
                }
            }
        }
        return result;
    }

    private int findMaximumPath(int x, int y) {
        int result =1;
        int nextX, nextY, temp;

        for (int i = 0; i < 4; i++) {
            temp = 0;
            nextX = x + X[i];
            nextY = y + Y[i];

            if (inForest(nextX, nextY) && forest[x][y] < forest[nextX][nextY]) {
                if ((temp = findMaximumPath(nextX, nextY)+1) > result) {
                    result = temp;
                }
            }
        }
        return result;
    }

    private boolean inForest(int x, int y) {
        return (x >= 0 && x < size && y >= 0 && y < size);
    }
}
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

Ruby

def max_trail(bamboos, n=[*0...bamboos.size])
  trees = n.product(n).map {|x,y| [y,x,bamboos[x][y]] }
  nexts = ->x,y,v { trees.select {|ex,ey,ev| (x-ex).abs+(y-ey).abs <2 && ev>v } }
  trail = ->xy,cnt=1,t=nexts[*xy] { t[0]? t.map {|e| trail[e,cnt+1] } : cnt }
  trees.map(&trail).flatten.max
end


Test
bamboos_1 = [ [0, 0],
              [0, 0] ]
expect(max_trail(bamboos_1)).to eq 1

bamboos_2 = [ [ 1, 6, 7],
              [ 2, 5, 8],
              [ 3, 4, 9] ] 
expect(max_trail(bamboos_2)).to eq 9 

bamboos_3 = [ [14, 9,12,10],
              [ 1,11, 5, 4],
              [ 7,15, 2,13],
              [ 6, 3,16, 8] ]            
expect(max_trail(bamboos_3)).to eq 4
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

풀이 작성

※ 풀이작성 안내
  • 본문에 코드를 삽입할 경우 에디터 우측 상단의 "코드삽입" 버튼을 이용 해 주세요.
  • 마크다운 문법으로 본문을 작성 해 주세요.
  • 풀이를 읽는 사람들을 위하여 풀이에 대한 설명도 부탁드려요. (아이디어나 사용한 알고리즘 또는 참고한 자료등)
  • 작성한 풀이는 다른 사람(빨간띠 이상)에 의해서 내용이 개선될 수 있습니다.
목록으로
코딩도장

코딩도장은 프로그래밍 문제풀이를 통해서 코딩 실력을 수련(Practice)하는 곳입니다.

다이나믹 프로그래밍 x 2
최장 증가 부분열(LIS) x 2
연관 문제

언어별 풀이 현황
전 체 x 16
cpp x 5
ruby x 2
python x 3
delphi x 1
기 타 x 2
java x 3