일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
- 알고리즘
- 백엔드 개발
- serializer
- 가가 형사 시리즈
- Django Restful API
- 웹 해킹
- Django CRUD
- Django Rest Framework
- 동적 프로그래밍
- 코딩공부
- Blind SQL Injection
- 삼성 SW 역량 테스트
- 일본 소설
- 웹 개발
- KITRI
- 백준
- 독서
- 추리 소설
- 백준알고리즘
- bob 9기 후기
- webhacking.kr
- 코딩
- best of the best
- 코딩 공부
- 히가시노 게이고
- DP
- 백준 알고리즘
- 백엔드
- bob
- 정보 보안
- Today
- Total
요모조모 ʚɞ
[C] 백준 1149번 : RGB거리 본문
오늘도 새로운 문제를 풀어보았습니다 !
분명 실버 1 정도의 난이도를 고른 건데,,,,
왜 여태 풀었던 DP 문제들 중 제일 어려웠던 걸까요? ( -᷅_-᷄)
(결국은 ,, 인터넷의 힘을 빌렸답니다.. ㅎㅎ)
.
https://www.acmicpc.net/problem/1149
저는 이 문제를 처음 봤을 땐 'dp 배열로 풀면 되겠다!' 라고 생각했습니다.
1번 집부터 N번까지 index를 증가시키면서 dp 배열을 update 해주면 최적화된 값이 나올 것이라 생각했기 때문입니다.
그래서 dp 1차원 배열을 만든 후, dp[집의 개수] = 최소 비용이라고 설정하였습니다.
그 이후 이전 집과 index만 겹치지 않게 dp 배열을 update 해주었습니다.
.
이렇게 코드를 작성하니 아래의 예시에서는 코드가 잘 작동하였습니다.
하지만 제가 임의로 작성해본 예시에 대해서는 틀린 답이 나왔습니다. ㅠ
제가 처음에 작성한 코드는 dp 배열을 1차원으로 만들었기 때문에 현재까지 탐색한 집 정보만 포함합니다.
따라서 집을 계속 탐색하다가 잘못된 값임을 (최솟값이 아님을) 알게 되더라도 이전으로 되돌릴 수 없습니다.
.
예시 1을 보면 1번 집에서 제일 작은 값인 26이 빨간색으로 칠할 때 드는 비용입니다. (첫 번째 index)
따라서 min 비교를 통해 dp[1]에 26을 저장하였습니다. (저는 배열을 1번 index부터 사용하였습니다.)
이렇게 되면 1번 집을 빨간색으로 칠한다고 확정 지어버리는 것입니다.
이 문제는 운이 좋아서 정답이 나왔지만, 예제 2를 보면 이 방식이 틀렸음을 확실히 알 수 있습니다.
.
제가 생각한 방식으로 예제 2를 보면, 1번 집에서는 최솟값인 10 (dp[1] = 10)을 선택합니다.
이후 1번 집을 색칠한 index(index 1)를 제외하고 생각했을 때 최솟값인 것은 1000(index 2)과 또 1000(index 3)입니다.
2번 집에는 9라는 적은 비용을 가진 색깔이 있지만,
dp[1]을 이미 10이라고 선택해버렸기 때문에 되돌아갈 수 없습니다.ㅠ
.
저는 이것을 어떻게 해결하면 좋을까.. 고민하다가 무작정 while 문을 사용해보았습니다.ㅎㅎㅎ
(N 범위 자체가 1000까지이고, 주어진 색깔이 3가지밖에 없어서 어쩌면 풀리지 않을까 싶었습니다...)
저는 모든 case를 다 계산해보고 min을 구해보았습니다.
여기서 반복 횟수를 줄이기 위해, 현재까지 구한 합이 현재 min보다 작으면 다음 반복을 하는 식으로 설정하였습니다.
제가 위에서 언급한 예시 2개와 몇 개의 간단한 예시를 돌려보았을 때는 답이 잘 나왔지만,
역시는 역시.. 시간 초과가 뜨더라구요ㅠㅠ..
(궁금하지 않겠지만..코드가 궁금하다면 더보기를 확인해주세요..ㅎ)
import java.util.Scanner;
class Main {
static int N;
static int[][] input=new int[1001][4];
static int[] visited=new int[1001];
static int[] sum=new int[1001];
static int min=1000*1000+1;
static int depth=1;
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner keyboard=new Scanner(System.in);
N=keyboard.nextInt();
for (int i=1; i<=N; i++)
for (int j=1; j<=3; j++)
input[i][j]=keyboard.nextInt();
keyboard.close();
outerloop:
while(true) {
visited[depth]++;
if (visited[depth-1]==visited[depth])
visited[depth]++;
while(visited[depth]>3) {
visited[depth]=0;
depth--;
if (depth<=0)
break outerloop;
visited[depth]++;
if (visited[depth-1]==visited[depth])
visited[depth]++;
}
sum[depth]=sum[depth-1]+input[depth][visited[depth]];
if (sum[depth]>=min)
continue;
depth++;
if (depth>N) {
if (sum[depth-1]<min)
min=sum[depth-1];
depth--;
}
}
System.out.println(min);
}
}
지금 작성한 코드를 좀 더 수정해볼까 싶었지만
문제 시간제한이 너무 짧기도 하고, 더 최적화할 부분을 찾기가 힘들었습니다.
그래서 인터넷에 다른 분들이 푼 알고리즘을 조금 참고해보았습니다.
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define MAX 1000*1000
int input[1001][4];
int dp[1001][4];
int min(int x, int y) {
return x < y ? x : y;
}
int main() {
int N;
scanf("%d", &N);
// 입력
for (int i = 1; i <= N; i++)
for (int j = 1; j <= 3; j++)
scanf("%d", &input[i][j]);
// dp 배열 채우기
dp[1][1] = input[1][1];
dp[1][2] = input[1][2];
dp[1][3] = input[1][3];
for (int i = 2; i <= N; i++) {
dp[i][1] = min(dp[i - 1][2], dp[i - 1][3]) + input[i][1];
dp[i][2] = min(dp[i - 1][1], dp[i - 1][3]) + input[i][2];
dp[i][3] = min(dp[i - 1][1], dp[i - 1][2]) + input[i][3];
}
// 출력
int min = MAX + 1;
for (int i = 1; i <= 3; i++)
if (dp[N][i] < min)
min = dp[N][i];
printf("%d", min);
return 0;
}
저는 그동안 dp 배열을 1차원으로 잡았었는데, 2차원으로 잡는 방법이 있더라구요...! 나 진짜 바본가ㅠ;
이렇게 되면 현재 구하는 index (여기서는 i)에서 R을 할 때, G를 택할 때, B를 택할 때를 모두 구할 수 있습니다.
그리고 i번째 집의 색깔을 정할 때, i-1번째 집을 확인합니다.
i번째 집 -> 빨간색(index 1)으로 칠하려면
i-1번째 집 -> 초록 색(index 2) 아니면 파란색(index 3)이어야 합니다.
따라서 i-1번째 집을 초록색, 파란색으로 칠했을 때의 비용 중 최솟값에 빨간색을 칠하는 비용을 더하면 됩니다.
=> dp[i][1] = min(dp[i-1][2], dp[i-1][3]) + input[i][1]
즉, 각 집마다 빨간색, 초록 색, 파란색을 칠하는 경우를 모두 고려한 후 조건에 맞게 활용하는 것입니다.
.
위의 예시 2번의 dp 배열을 구해보면 다음과 같습니다.
{ }에 적힌 부분은 1번 집부터 선택한 색깔의 index 입니다.
(ex. dp[2][1] -> 1번 집 2번 index (초록 색), 2번 집 1번 index (빨간색) 선택)
이렇게 dp 배열을 채운 후 dp[N][1] ~ dp[N][3] 중 최솟값을 찾으면 됩니다!
.
DP는 정말 왜 이렇게 어려운 걸까요?...^^
앞으로 한참은 더 풀어봐야 할 것 같습니다...
'코딩 > C' 카테고리의 다른 글
[C] 백준 17471번 : 게리맨더링 (0) | 2020.05.04 |
---|---|
[C] 백준 17070번 : 파이프 옮기기 1 (0) | 2020.05.02 |
[C] 백준 2294번 : 동전 2 (0) | 2020.04.30 |
[C] 백준 1915번 : 가장 큰 정사각형 (0) | 2020.04.29 |
[C] 백준 7579번 : 앱 (0) | 2020.04.28 |