[DP] 백준 문제 풀이 - 17404 RGB거리 2

2022. 7. 9. 00:03· PS 연습
목차
  1. 👩🏻‍💻 문제링크
  2. ✍️ 아이디어

👩🏻‍💻 문제링크

https://www.acmicpc.net/problem/17404

 

17404번: RGB거리 2

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

www.acmicpc.net

 

✍️ 아이디어

1. 문제 이해

  • RGB 거리 1과 비슷해 보이지만 마지막 집이 첫번째 집과 이웃한다는 점이 다르다
  • 가장 싸게 모든 집을 페인트칠 하는 알고리즘 근데 인접한 집은 다른 색으로 페인트칠 해야함
  • 앞집이 빨초파 인 경우로 나눠야함 앞집이 빨간색이면 다음집은 초록과 파란집중에 작은것을 골라야함

2. 난 처음에 백트래킹 처럼 어떤 집을 선택하였는지 싹다 기록하려고 하였으나 쉽지않음 

3. 그저 맨 앞집이 빨간집,초록집,파란집인 경우를 각각 반복문으로 굴려주면 된다(맨 앞집을 고정!!!)

ex)맨 앞집이 빨간집이면 마지막 집에서 초록 파란집중에 골라야함

 

4. 강의 안들었으면 못풀었을듯, 처음 집을 고를때  min에 선택되지 않도록 매우 큰 수를 넣는 구현 방법을 생각 못했을것 같다

 

5. 내가 생각한것중에 하나가 2~n-1번째 까지 구하고 마지막 1,n번째를 더해서 최솟값을 구하는거였는데 이건 반례가 있을듯

(경우의 수)

1. 1번집이 R이고 마지막집이 R일때 최소비용(x)

2. 1번집이 R이고 마지막집이 G일때 최소비용

3. 1번집이 R이고 마지막집이 B일때 최소비용

4. 1번집이 G이고 마지막집이 R일때 최소비용

5. 1번집이 G이고 마지막집이 G일때 최소비용(x)

6. 1번집이 G이고 마지막집이 B일때 최소비용

7. 1번집이 B이고 마지막집이 R일때 최소비용

8. 1번집이 B이고 마지막집이 G일때 최소비용

9. 1번집이 B이고 마지막집이 B일때 최소비용(x)

✍️소스코드

  • 내 코드 + 강의 참조
#include <iostream>
#include <algorithm>
using namespace std;

long long result[1001][3];
long long color[1001][3];

int main()
{
	int n; cin>>n;
	long long ans = 10000001;
	for(int i=1; i<=n; i++)
	{
		for(int j=0; j<=2; j++)
		{
			cin>>color[i][j];
		}	
	}
	
	for(int first=0; first<=2; first++) //첫집이 빨간경우, 초록경우, 파란경우를 나눔
	{
		for(int i=0; i<=2; i++)//첫집 색칠하기
		{
			if(first==i)
				result[1][i]=color[1][i];
			else{
				result[1][i]=10000001; // 조건이 아닌경우 min에서 선택되지않기 위해 큰수를 넣음
			}
		}
		
		for(int i=2; i<=n; i++)
		{
			result[i][0]=color[i][0]+min(result[i-1][1],result[i-1][2]);
			result[i][1]=color[i][1]+min(result[i-1][0],result[i-1][2]);
			result[i][2]=color[i][2]+min(result[i-1][1],result[i-1][0]);
		}
		
		for(int i=0; i<=2; i++) //마지막 집 색칠하기
		{
			if(first==i) continue;
			ans=min(ans, result[n][i]);
		}	
	}
	
	cout<<ans<<'\n';
}

 

 

체감난이도 걸린시간 참고 사용 문법
상 1hour 강의 참고 이차원 DP

'PS 연습' 카테고리의 다른 글

[완전 탐색] 백준 문제 풀이 - 1476 날짜 계산  (0) 2022.07.10
[완전 탐색] 백준 문제 풀이 - 3085 사탕 게임  (0) 2022.07.10
[DP] 백준 문제 풀이 - 11054 가장 긴 바이토닉 부분 수열  (0) 2022.07.06
[DP] 백준 문제 풀이 - 2156 포도주 시식  (0) 2022.07.03
[DP] 백준 문제 풀이 - 9465 스티커  (0) 2022.07.02
  1. 👩🏻‍💻 문제링크
  2. ✍️ 아이디어
'PS 연습' 카테고리의 다른 글
  • [완전 탐색] 백준 문제 풀이 - 1476 날짜 계산
  • [완전 탐색] 백준 문제 풀이 - 3085 사탕 게임
  • [DP] 백준 문제 풀이 - 11054 가장 긴 바이토닉 부분 수열
  • [DP] 백준 문제 풀이 - 2156 포도주 시식
생선묵김치찌개
생선묵김치찌개
생선묵김치찌개
준혁's 코딩 연구기록
생선묵김치찌개
전체
오늘
어제
  • 분류 전체보기 (96)
    • Java (5)
    • Spring Boot (3)
    • 자료구조 (8)
    • 네트워크 (4)
    • 데이터베이스 (4)
    • 기술적 고민 (17)
      • Side Match (13)
      • 자리나따 (4)
    • C++ (3)
    • Algorithm (4)
    • PS 연습 (38)
    • 잡동사니 (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 브루트 포스
  • dp
  • 백준
  • 열혈 자료구조
  • 재귀
  • 원형 연결 리스트
  • Stream
  • 알고리즘
  • 백준 골드
  • sentry
  • 자료구조
  • 스택
  • 큐
  • DN
  • 파일 업로드
  • 스프링
  • ㄱ
  • 해커톤
  • CPP
  • open api
  • 수식트리
  • 단순 연결 리스트
  • backend
  • 완전탐색
  • 이진트리
  • aws rds
  • 예외처리
  • 트리
  • 양방향 연결 리스트
  • 배열 리스트

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.1
생선묵김치찌개
[DP] 백준 문제 풀이 - 17404 RGB거리 2
상단으로

티스토리툴바

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

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