고도고도
🍎🍏
고도고도
전체 방문자
7,931
오늘
11
어제
26
  • 분류 전체보기 (149) N
    • 🔨 프로젝트 (0)
      • TP 1 (0)
      • WhiteHCCTV (0)
      • FootPrint (0)
    • 💻 개발 (43) N
      • TIL (16)
      • Android (6)
      • Kotlin (4)
      • Flutter (9) N
      • Node.js (5)
      • Error (3) N
    • ✏️ 알고리즘 (6)
      • Graph (6)
      • String (0)
      • Sort (0)
    • ✍️ 코테 준비 (44)
      • Math (1)
      • Implementation (3)
      • String (3)
      • Brute Force (5)
      • Back Tracking (7)
      • Greedy (0)
      • Dynamic Programming (13)
      • Binary Search (1)
      • DFS, BFS (5)
      • Shortest Path (2)
      • Two Pointer (4)
      • MST (0)
    • 📚 CS (6)
      • Operating System (6)
    • ⛹️ 라이프 (50)
      • 2020 겨울방학 모칵코(팀) (13)
      • 2020 겨울방학 모각코(개인) (13)
      • 2021 여름방학 모칵코(팀) (8)
      • 2021 여름방학 모각코(개인) (7)
      • 코딩 테스트 (1)
      • 회고 (7)

블로그 메뉴

  • 홈
  • 깃허브
  • 링크드인

인기 글

  • [TIL] 22.03.13
    2022.03.13
    [TIL] 22.03.13
  • [문자열 / Kotlin] 2020 KAKAO⋯
    2022.03.11
    [문자열 / Kotlin] 2020 KAKAO⋯
  • [TIL] 22.03.20
    2022.03.20
    [TIL] 22.03.20
  • [퍼듀 일기] 어느덧 한 달째
    2022.03.01
    [퍼듀 일기] 어느덧 한 달째
  • [퍼듀 일기] 적응 완료
    2022.03.05
    [퍼듀 일기] 적응 완료

최근 글

  • [Flutter] ModalBottomSheet가⋯
    2022.08.09
    [Flutter] ModalBottomSheet가⋯
  • [Error / Gradle] The current⋯
    2022.08.09
    [Error / Gradle] The current⋯
  • [Flutter / Dart] What is Equa⋯
    2022.08.06
    [Flutter / Dart] What is Equa⋯
  • [Flutter] BLoC 패턴으로 자동⋯
    2022.07.26
    [Flutter] BLoC 패턴으로 자동⋯
  • [Flutter / Dart] What is Sing⋯
    2022.07.21
    [Flutter / Dart] What is Sing⋯

최근 댓글

  • 잘보고 갑니다~
    개갓세
  • 좋은 글이네요
    날인로세
  • 잘 보고 갑니다^^
    프로퍼티
hELLO · Designed By 정상우.
고도고도

🍎🍏

[동적 계획법 1] [C++] 1149번. RGB 거리
✍️ 코테 준비/Dynamic Programming

[동적 계획법 1] [C++] 1149번. RGB 거리

2021. 1. 13. 13:47

www.acmicpc.net/problem/1149

 

1149번: RGB거리

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나

www.acmicpc.net

 

 

입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.


해결 방법

이 문제의 시간 제한은 0.5초로 짧다.

중첩 반복문을 이용한 브루트 포스의 방법으론 통과할 수 없다는 의미이다.

dp로 문제를 해결하기 위해선 점화식, 즉 규칙을 찾아내야한다.

 

입력 값으로 행은 2 ~ 1000까지 최대 999개의 행이 주어지고,

열은 0, 1, 2로 총 3개의 열이 주어진다.

 

이 문제의 핵심은 행의 최소 값을 다음 행의 원소와 더하되 열이 같지 않은 원소에 더해야 한다는 것이다.

 

입력 값이 저장된 배열을 house라고 했을 때

이를 점화식으로 구현하면

dp[n][0] = min(dp[n-1][1], dp[n-1][2]) + house[n][0]

dp[n][1] = min(dp[n-1][0], dp[n-1][2]) + house[n][1]

dp[n][2] = min(dp[n-1][0], dp[n-1][1]) + house[n][2]

가 된다.

 

위 과정을 모든 행에 대해서 반복하면 마지막 행에는 각 열에서의 최소값들이 담겨 있다.

이 값들 중에서 가장 작은 값을 출력하면 정답.

 

 

해결 과정

점화식을 코드로 구현하고 마지막 행에서 최소값을 찾는 코드를 추가한다.

 

최종 코드는

 

#include <iostream>
using namespace std;

int min(int a, int b){
    return a < b ? a : b;
}

int main(){
    int n, a, b, c, result;
    int house[999][3];
    int dp[999][3];
    
    cin >> n;
    
    for(int i = 0; i < n; i++){
        cin >> a >> b >> c;
        house[i][0] = a;
        house[i][1] = b;
        house[i][2] = c;
    }
    
    dp[0][0] = house[0][0];
    dp[0][1] = house[0][1];
    dp[0][2] = house[0][2];
    
    for(int i = 1; i < n; i++){
        dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + house[i][0];
        dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + house[i][1];
        dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + house[i][2];
    }
    
    result = dp[n-1][0];
    for(int i = 1; i < 3; i++){
        if (result > dp[n-1][i]){
            result = dp[n-1][i];
        }
    }
    
    cout << result;
    
    return 0;
}

 

min 함수는 더 작은 값을 return 해주는 함수이다.

저작자표시

'✍️ 코테 준비 > Dynamic Programming' 카테고리의 다른 글

[동적 계획법 1] [C++] 2579번. 계단 오르기  (0) 2021.01.14
[동적 계획법 1] [C++] 1932번. 정수 삼각형  (0) 2021.01.13
[동적 계획법 1] [C++] 1149번. RGB 거리  (0) 2021.01.13
[동적 계획법 1] [C++] 9461번. 파도반 수열  (0) 2021.01.13
[동적 계획법 1] [Python] 1904번. 01타일  (0) 2021.01.12
[동적 계획법 1] [Python] 9184번. 신나는 함수 실행  (0) 2021.01.12
    '✍️ 코테 준비/Dynamic Programming' 카테고리의 다른 글
    • [동적 계획법 1] [C++] 2579번. 계단 오르기
    • [동적 계획법 1] [C++] 1932번. 정수 삼각형
    • [동적 계획법 1] [C++] 9461번. 파도반 수열
    • [동적 계획법 1] [Python] 1904번. 01타일
    C++, 동적 계획법 1, 백준
    고도고도
    고도고도
    좋아하는 것을 하자\n 스위프트 찍먹중\n 광고 없는 블로그
    댓글쓰기
    다음 글
    [동적 계획법 1] [C++] 1932번. 정수 삼각형
    이전 글
    [동적 계획법 1] [C++] 9461번. 파도반 수열
    • 이전
    • 1
    • ···
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 다음