반응형
rolypolytoy
현's story
rolypolytoy
전체 방문자
오늘
어제
  • 분류 전체보기
    • 현's tory
      • 여행
      • 개인사업
      • 컨프런스
      • 채용지원
    • Vision AI | 3D Graphics
      • Vision AI
      • OpenGL
    • 프로그래밍 언어
      • C++
      • Python
    • Computer Science
      • 운영체제
    • 알고리즘
      • 백준
      • 프로그래머스
      • 개념정리
    • 유용한 링크
      • 개발

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 백준알고리즘
  • 백준문제풀이
  • iOS비동기
  • 백준
  • 백준1756
  • sync
  • iOSMetal
  • DFS조합
  • 사회망서비스
  • 백준사회망서비스
  • 상표특허출원
  • openglvscode
  • 알고리즘구현
  • 백준2169
  • c++
  • 아키텍처패턴
  • 백준이분탐색
  • 백준다이나믹
  • 백준13397
  • 백준17471
  • 알고리즘
  • vscodeopengl
  • 백준2533
  • 디자인패턴
  • 백준2302
  • 프로그래머스실패율
  • 다이나믹프로그래밍
  • PlantUML
  • EffectiveC++
  • IOS

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
rolypolytoy
알고리즘/백준

[백준 2096] 내려가기 C++

[백준 2096] 내려가기 C++
알고리즘/백준

[백준 2096] 내려가기 C++

2021. 1. 21. 20:16
반응형

www.acmicpc.net/problem/2096

 

2096번: 내려가기

첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다.

www.acmicpc.net

 

이번 문제는 다이나믹 프로그래밍 문제로, 기존의 다이나믹 문제 유형과 비슷하지만,

메모리를 효율적으로 구성해야하는 문제입니다.

 

메모리를 효율적으로 사용하기 전에,

기존의 간단한 방법으로 문제를 풀면

 

배열을 arr[n][3] 배열에서 이전의 위치에서 arr[n][0~3]에 더 해질 수 있는 칸들(arr[n-1][0~3] 중에서 최댓값을 구해서 arr[n][0~3]에 더해주면 됩니다.

 

문제에서는 

별    
가능 가능 불가능

 

이렇게 나와있어서, 별이 가능한 칸에 움직일 수 있습니다.

이것을 반대로 생각해서

첫 번째 칸에 올 수 있는 별의 위치를 구하면 됩니다. 

즉,

 

O별 O별 X불가능
여기칸에 올 수 있는 별    

이렇게 문제를 바꿔서 생각하면 됩니다.

 

메모리가 4MB로 제한이 되어있는데, 메모리 제한만 풀린다면 다음 코드가 정답으로 인정이 될것입니다.

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;


const int MAX = 100001;

//const int MAX = 10;





void solution(){

    int dp[MAX][3] = {0, };
    int map[MAX][3] = {0, };

    int n;
    
    cin >> n;

    for (int i = 1; i <= n; i++){
        cin >> map[i][0] >> map[i][1] >> map[i][2];
    }

    //max값찾기

    for (int i = 1; i <= n; i++){
        dp[i][0] = max(dp[i-1][0], dp[i-1][1]) + map[i][0];
        dp[i][1] = max(dp[i-1][0], max(dp[i-1][1], dp[i-1][2])) + map[i][1];
        dp[i][2] = max(dp[i-1][1], dp[i-1][2]) + map[i][2];
    }

    int maxV = max(dp[n][0], max(dp[n][1], dp[n][2]));

    memset(dp, 0, sizeof(dp));

    for (int i = 1; i <= n; i++){
        dp[i][0] = min(dp[i-1][0], dp[i-1][1]) + map[i][0];
        dp[i][1] = min(dp[i-1][0], min(dp[i-1][1], dp[i-1][2])) + map[i][1];
        dp[i][2] = min(dp[i-1][1], dp[i-1][2]) + map[i][2];
    }
    
    int minV = min(dp[n][0], min(dp[n][1], dp[n][2]));


    cout << maxV << " " << minV << '\n';
}
int main(){


    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    solution();

    return 0;
}

 

 

하지만, 이 코드의 경우,

dp[100001][3]의 메모리를 사용해야하기 때문에 약 4MB 이상의 메모리가 필요합니다.

 

간단하게 위와같이 풀수 있지만, 문제에서 제한 조건은 메모리 4MB이하로 문제를 해결하라고 해서

 

필요 없는 공간 빼고 진짜 필요한 메모리만 잡아서 풀게 된다면 4MB메모리를 사용해서 풀 수 있습니다.

즉, 현재 진행되야하는 메모리 3 공간 + 이전의 진행했던 공간 3이 있으면 됩니다.

max와 min을 한꺼번에 계산하고 싶다면, 현재 진행되어야 하는 메모리 max 3공간 + 현재 진행되어야하는 메모리 min 3공간 + 이전에 진행했던 공간 3공간(temp배열 or 변수)를 선언한다면, 메모리를 엄청나게 줄일 수 있습니다.

 

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;


void solution(){

    int n;
    int maxV, minV;
    int mind[3] = {0, };
    int maxd[3] = {0, };
    int input[3] = {0, };


    cin >> n;

    cin >> maxd[0] >> maxd[1] >> maxd[2];
    mind[0] = maxd[0];
    mind[1] = maxd[1];
    mind[2] = maxd[2];

    for (int i = 1; i < n; i++){
        cin >> input[0] >> input[1] >> input[2];

        int temp0 = maxd[0];
        int temp1 = maxd[1];
        int temp2 = maxd[2];

        maxd[0] = max(temp0, temp1) + input[0];
        maxd[1] = max(temp0, max(temp1, temp2)) + input[1];
        maxd[2] = max(temp1, temp2) + input[2];

        temp0 = mind[0];
        temp1 = mind[1];
        temp2 = mind[2];

        mind[0] = min(temp0, temp1) + input[0];
        mind[1] = min(temp0, min(temp1, temp2)) + input[1];
        mind[2] = min(temp1, temp2) + input[2];

        

    }

    maxV = max(maxd[0], max(maxd[1], maxd[2]));
    minV = min(mind[0], min(mind[1], mind[2]));

   

    cout << maxV << " " << minV << '\n';
}
int main(){


    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    solution();

    return 0;
}

반응형
저작자표시 비영리 변경금지

'알고리즘 > 백준' 카테고리의 다른 글

[백준 9252] LCS 2 C++  (0) 2021.01.21
[백준 9251] LCS C++  (0) 2021.01.21
[백준 1707] 이분 그래프 C++  (0) 2021.01.11
[백준 11660] 구간 합 구하기 5 C++  (0) 2021.01.10
[백준 2178] 미로 탐색 Swift  (0) 2020.11.27
    '알고리즘/백준' 카테고리의 다른 글
    • [백준 9252] LCS 2 C++
    • [백준 9251] LCS C++
    • [백준 1707] 이분 그래프 C++
    • [백준 11660] 구간 합 구하기 5 C++
    rolypolytoy
    rolypolytoy

    티스토리툴바

    단축키

    내 블로그

    내 블로그 - 관리자 홈 전환
    Q
    Q
    새 글 쓰기
    W
    W

    블로그 게시글

    글 수정 (권한 있는 경우)
    E
    E
    댓글 영역으로 이동
    C
    C

    모든 영역

    이 페이지의 URL 복사
    S
    S
    맨 위로 이동
    T
    T
    티스토리 홈 이동
    H
    H
    단축키 안내
    Shift + /
    ⇧ + /

    * 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.