골랜디 #2 2342번
Published at: 2025-03-21
Last modified at: 2025-03-21
안녕하세요 한라나입니다.
문제 푸는데 좀 걸려서 12시를 넘어버렸지만, 솔브닥 스트릭은 오전 6시 기준이니까 괜찮을거에요..
오늘 문제 제목은 아래와 같습니다.
골드3! DP! 스탠다드!! 하루에 하나씩 가벼운 마음으로 풀만한 문제는 아닌 것 같죠?
고생 많이 했..긴 한데, 사실 제가 멍청해서 했습니다.
풀이 자체는 바로 생각해냈고 맞는 풀이였는데, 그냥…너무 성급한 일반화를 해버렸습니다.
끝난 상태는 항상 서로 다른 마지막 두 개의 수일거라거나, 기타등등.
참고로 이 문제는 1번테케부터 이 조건이 맞지 않아서 저렇게 풀면 1%를 벗어날수가 없습니다. 출제자 참 나쁜 사람…
DP의 정석같은 문제이고, 정석대로 풀면 됩니다. 저는 탑다운 방식(재귀)로 풀었습니다.
기본 개념은 현재 상태(어느 발이 어느 발판에 있는지)와 현재 턴이 있을때, 바로 이전 턴으로 가능한 모든 상태에 대해서 함수를 불러오고, 거기에 각각 이동 비용을 얹은 다음, 그중에서 최소값을 dp 배열에 저장해놓고 리턴해주면 됩니다.
그러니까 턴을 역행하는 거에요! 아래 설명은 모두 역행을 기준으로 설명합니다.
이 가능한 모든 상태를 구분하는 것이 까다로워서 골드 3 정도에 안착한 것 같습니다.
전 딴데서 헤멨지만요
그러니까, 가장 중요한 재귀 함수부터 보겠습니다. 입력은 현재 턴, 왼발 위치, 오른발 위치입니다.
int calc(int turn, int L, int R)
dp 배열에 값이 있다면 계산하지말고 그걸 바로 내놓으면 됩니다.
if(dp[turn][L][R]!=0) return dp[turn][L][R];
1턴 째의 비용은 중앙에서 꺼내오는 경우의 수밖에 없기 때문에, 2를 리턴해줍니다. 이게 최소 단위입니다.
if(turn==1) return 2;
이전 턴에서 눌러야 하는 버튼과 이번 턴에서 눌러야 하는 버튼이 같았다면, 두 발 모두 움직이지 않고 눌러야 하는 버튼만 까딱했을겁니다.
그래서 발 위치는 옮기지 않고, 비용 1만 추가해서 dp 배열에 넣어주고 리턴합니다.
if(position[turn-1]==position[turn]) {
dp[turn][L][R] = calc(turn-1, L, R) + 1;
return dp[turn][L][R];
}
문제를 잘 읽어보면, 중앙에 있는 발이 나올 순 있지만 나온 발이 중앙으로 들어갈 수는 없다는 것을 알 수 있습니다.
우리는 턴을 역행하고 있기 때문에, 만약 현재 한쪽 발이 중앙에 들어가있다면 그 재귀가 끝날때까지 그 발은 항상 중앙에만 있을 거에요.
그렇기 때문에 나와있는 발이 이전 턴에서 눌러야 하는 버튼 위에 있다면 발을 옮기지 않고 1을 더한 수를, 그게 아니라면 이전 턴에서 눌러야 하는 버튼으로 나와있는 발을 옮겨주고 비용을 더한 수를 리턴하면 됩니다.
비용은 한 칸 떨어져있으면 3, 두 칸 떨어져 있으면 4인데, 출발지와 목적지를 뺀 값에 안전하게 2의 배수인 8 정도를 더해주고 2로 나눈 나머지를 구해보면 몇 칸 떨어져 있는지 나옵니다.
1칸일 때 3이어야 하기 때문에, 이 값은 빼줍니다.
if(L==0) {
if(position[turn-1]==R) dp[turn][L][R] = calc(turn-1, L, R) + 1;
else dp[turn][L][R] = calc(turn-1, L, position[turn-1]) + 4 - ((R-position[turn-1]+8)%2);
return dp[turn][L][R];
}
//L과 R을 바꿔서 같은 if문이 있어야 합니다.
다음은, 한 발이 이전 턴에 눌러야 하는 버튼 위에 있는 경우입니다.
이경우에 다른 발은 이전 턴에 눌러야 하는 버튼을 제외한 다른 모든 위치에 존재하다가, 이전 턴에서 현재 턴으로 넘어오면서 현재 턴에 눌러야 하는 버튼을 눌렀을 수 있습니다.
그래서 0부터 4까지 살펴보면서, 거리에 따라서 힘 값을 다르게 더한채로 모두 비교해 봅니다.
다만 제가 able이라는 배열을 만들었는데, 이 배열은 해당하는 버튼이 ‘처음’ 나온 턴을 의미합니다.
이 턴 전에는 해당하는 버튼 위에 발이 없었어야만 하기 때문에, 해당하는 버튼이 처음 나온 턴과 그 이후 턴에서만 발을 그곳에 둘 수 있습니다.
int value = 2147482647;
if(position[turn-1]==L) {
int j;
for(j=0;j<5;j++) {
if((j!=L)) {
if(able[j]<=turn-1) {
if(j==0) value = min(value, calc(turn-1, L, j) + 2);
else if(j==R) value = min(value, calc(turn-1, L, R) + 1);
else if((R-j+8)%2==1) value = min(value, calc(turn-1, L, j) + 3);
else value = min(value, calc(turn-1, L, j) + 4);
}
}
}
dp[turn][L][R] = value;
return value;
}
//L과 R을 바꿔서 같은 if문이 있어야 합니다.
이 모든 경우의 수를 빗겨갔다면, 두 발은 모두 1234 중에 하나에 각각 위치하면서 이전 턴에서 눌러야 했던 버튼 위에는 현재 발이 없다는 이야기입니다.
그렇다는 말은, 현재 턴에서 눌러야 하는 버튼 위에 있지 않은 발은 고정되어 있고, 버튼 위에 있는 발은 이전 턴에서 눌러야 했던 버튼 위에 있다가 현재 턴에서 이동해서 눌렀다고 생각해야 합니다.
따라서 아래와 같이 해줍니다.
if(position[turn]==L) value = calc(turn-1, position[turn-1], R) + 4 - ((L-position[turn-1]+8)%2);
else value = calc(turn-1, L, position[turn-1]) + 4 - ((R-position[turn-1]+8)%2);
dp[turn][L][R] = value;
return value;
여기까지 calc 함수를 봤습니다. 메인함수 안에서는 수열을 받아 저장하고 calc 함수를 실행시킨 다음 최솟값을 찾으면 됩니다.
다만 처음부터 끝까지 한 발판만 누르는 경우는 그냥 턴 수 + 1을 출력하면 되고, 입력 받을때 able 배열을 저장해야 합니다.
또 마지막으로 누른 버튼은 당연히 마지막 상태에 들어가지만, 남은 한쪽 발은 무슨 버튼을 누르고 있는 것이 최적해인지 모르기 때문에 한 번이라도 눌린 버튼이 있다면 경우의 수에 넣고 봅니다.
이 두 조건을 확인하려면 입력 받을때 1번, 2번, 3번, 4번 버튼이 각각 눌린적이 있는지도 입력 받을때 확인하면 되겠습니다. 저는 number[] 배열로 확인했습니다.
따라서 버튼 네 개가 모두 한번 이상씩 눌렸다면 세 번의 calc, 세 개만 눌렸다면 두 번의 calc,… 와 같이 돌려서 대소를 비교해줍니다.
int last = position[i];
int j;
int ans = 2147482647;
for(j=1;j<=4;j++) {
if(j!=last) {
if(numbers[j]!=0) ans = min(ans, calc(i, last, j));
}
}
printf("%d", ans);
골드 3의 저력 무섭네요.
감사합니다.
전체 코드
#include <stdio.h>
//using namespace std;
int position[100102];
int dp[100102][5][5];
int able[5];
int i = 1;
int power(int a, int n) {
int ans = 1;
int i;
for(i=0;i<n;i++) ans *= a;
return ans;
}
int min(int a, int b) {
if(a>b) return b;
else return a;
}
int calc(int turn, int L, int R) {
if(dp[turn][L][R]!=0) return dp[turn][L][R];
if(turn==1) return 2;
if(position[turn-1]==position[turn]) {
dp[turn][L][R] = calc(turn-1, L, R) + 1;
return dp[turn][L][R];
}
if(L==0) {
if(position[turn-1]==R) dp[turn][L][R] = calc(turn-1, L, R) + 1;
else dp[turn][L][R] = calc(turn-1, L, position[turn-1]) + 4 - ((R-position[turn-1]+8)%2);
return dp[turn][L][R];
}
if(R==0) {
if(position[turn-1]==L) dp[turn][L][R] = calc(turn-1, L, R) + 1;
else dp[turn][L][R] = calc(turn-1, position[turn-1], R) + 4 - ((L-position[turn-1]+8)%2);
return dp[turn][L][R];
}
int value = 2147482647;
if(position[turn-1]==L) {
int j;
for(j=0;j<5;j++) {
if((j!=L)) {
if(able[j]<=turn-1) {
if(j==0) value = min(value, calc(turn-1, L, j) + 2);
else if(j==R) value = min(value, calc(turn-1, L, R) + 1);
else if((R-j+8)%2==1) value = min(value, calc(turn-1, L, j) + 3);
else value = min(value, calc(turn-1, L, j) + 4);
}
}
}
dp[turn][L][R] = value;
return value;
}
if(position[turn-1]==R) {
int j;
for(j=0;j<5;j++) {
if((j!=R)) {
if(able[j]<=turn-1) {
if(j==0) value = min(value, calc(turn-1, j, R) + 2);
else if(j==L) value = min(value, calc(turn-1, L, R) + 1);
else if((L-j+8)%2==1) value = min(value, calc(turn-1, j, R) + 3);
else value = min(value, calc(turn-1, j, R) + 4);
}
}
}
dp[turn][L][R] = value;
return value;
}
if(position[turn]==L) value = calc(turn-1, position[turn-1], R) + 4 - ((L-position[turn-1]+8)%2);
else value = calc(turn-1, L, position[turn-1]) + 4 - ((R-position[turn-1]+8)%2);
dp[turn][L][R] = value;
return value;
}
int main() {
short numbers[5];
while(1) {
scanf("%d", &position[i]);
if(position[i]==0) break;
numbers[position[i]] = 1;
if(able[position[i]]==0) able[position[i]] = i;
i++;
}
i--;
if(numbers[1]+numbers[2]+numbers[3]+numbers[4]==1) {
printf("%d", i+1);
return 0;
}
int last = position[i];
int j;
int ans = 2147482647;
for(j=1;j<=4;j++) {
if(j!=last) {
if(numbers[j]!=0) ans = min(ans, calc(i, last, j));
}
}
printf("%d", ans);
return 0;
}