[Algorithm] Programmers :: 숫자 타자 대회
https://school.programmers.co.kr/learn/courses/30/lessons/136797
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
int dp[100001][10][10];
string targetNumbers;
int cost[10][10] = {
{ 1, 7, 6, 7, 5, 4, 5, 3, 2, 3 },
{ 7, 1, 2, 4, 2, 3, 5, 4, 5, 6 },
{ 6, 2, 1, 2, 3, 2, 3, 5, 4, 5 },
{ 7, 4, 2, 1, 5, 3, 2, 6, 5, 4 },
{ 5, 2, 3, 5, 1, 2, 4, 2, 3, 5 },
{ 4, 3, 2, 3, 2, 1, 2, 3, 2, 3 },
{ 5, 5, 3, 2, 4, 2, 1, 5, 3, 2 },
{ 3, 4, 5, 6, 2, 3, 5, 1, 2, 4 },
{ 2, 5, 4, 5, 3, 2, 3, 2, 1, 2 },
{ 3, 6, 5, 4, 5, 3, 2, 4, 2, 1 }
};
int DFS(int index, int left, int right)
{
if (index == targetNumbers.size()) return 0;
if (dp[index][left][right] != -1) return dp[index][left][right];
int result = 0x3f3f3f3f;
int targetNum = targetNumbers[index] - '0';
if (targetNum != right) // 이동해야할 버튼에 오른손이 안올라가져 있다면
{
// 왼손이동
result = min(result, DFS(index + 1, targetNum, right) + cost[left][targetNum]);
}
if (targetNum != left) // 이동해야할 버튼에 왼손이 안올라가져 있다면
{
// 오른손이동
result = min(result, DFS(index + 1, left, targetNum) + cost[right][targetNum]);
}
return dp[index][left][right] = result;
}
int solution(string numbers)
{
targetNumbers = numbers;
memset(dp, -1, sizeof(dp));
return DFS(0,4,6);
}
|
cs |
그리디하게 풀릴줄알고 처음에는 그리디한 코드를 작성했었다.
거진 맞긴했는데, 일부 케이스는 아예 틀리고 시간초과도 나왔었다.
가만히 생각해보니, 현재 위치에서 타겟위치까지의 가중치값을 비교해서 왼손을 옮길지 오른손을 옮길지 결정했었는데 값이 같을 경우 그냥 둘 다 탐색하게 했었다. 그러니 당연히 시간초과가 나올 수 밖에 없다.
틀린케이스에 대해서는 그냥 그리디한 접근자체가 잘못됐다는 거다. 무조건 가까운손으로 옮기는게 아니라, 일단 먼거를 먼저 옮기더라도 그게 정답이 될 수 있는 루트인 경우가 존재한다는 것이다.
그래서 dp풀이를 참고했고, dp의 각 요소는 다음과같다.
dp[index][L][R] == 타겟숫자의 index번째에서 왼손은 L번, 오른손은 R번에 있을때, 타겟숫자를 완성하기위한 최소가중치값.
각 호출에서 왼쪽,오른쪽 둘 다 비교해서 최솟값을 넣기때문에 '확실하게' dp값에는 최솟값이 들어가있다는게 보장되어진다. 그렇기 때문에 다른루트에서 접근했을 때 그대로 그 값을 리턴해주면 된다.
이동해야할 버튼에 이미 다른 손가락이 있다면 그 손가락으로 눌러야한다..라는게 조건이니 적절한 조건문을 거는것을 잊으면 안된다.