프로그래머스 숫자 타자 대회
문제 URL : https://school.programmers.co.kr/learn/courses/30/lessons/136797
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제 접근법 : 알고리즘만 설명하자면 다익스트라 + DP 문제입니다.
하지만 다익스트라는 없어도 되긴합니다. 손으로 일일이 0~9까지 최단거리고 구하는 방법을 일일이 구한다면
이와같이 나오는 2차월 배열을 미리 선언하셔도됩니다. 그치만 대회나 코딩테스트같은데서 시간이 부족한데
손으로 일일이 저걸 만들 시간이 부족하겠죠?
빠르게 알고리즘으로 짜서 최소거리를 구하는게 더빠르다면 그걸 써먹는게 낫겠죠
그래서 저는 빠르게 다익스트라를 이용해서 모든경로의 최단시간을 구해서 저장해놓은다음 문제를 생각했습니다.
왼쪽 엄지손가락은 4에 있고 오른쪽 엄지손가락은 6에있으니
왼쪽이든 오른쪽이든 반드시 하나만 움직여서 그거리만큼 더해보면서 백트래킹으로 모든경우의 수를 구합니다.
알고리즘만 잘 짠다면 백트랭킹은 어렵지않게 짤수있습니다. 거기에 메모이제이션 기법만 이용하면 dp는 완성됩니다.
그러나 하나 주의할게
조건을 잘 확인해야 하는게
단, 숫자 자판은 버튼의 크기가 작기 때문에 같은 숫자 버튼 위에 동시에 두 엄지 손가락을 올려놓을 수 없습니다. 즉, 어떤 숫자를 눌러야 할 차례에 그 숫자 위에 올려져 있는 손가락이 있다면 반드시 그 손가락으로 눌러야 합니다.
이조건을 잘지켜줘야한다는것 왼쪽엄지가 해당숫자에 있다고해도 오른쪽엄지가 해당숫자로와서 눌러버리면 같은숫자에 있는걸 피하게끔해야합니다. 해당숫자에 위치한다면 그대로 누를수있도록
소스코드 :
|
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
|
#include<bits/stdc++.h>
using namespace std;
int num[12][12];//숫자들의 최단거리
int dy[8]={-1,-1,0,1,1,1,0,-1};
int dx[8]={0,1,1,1,0,-1,-1,-1};
char dial[4][3]={{1,2,3},{4,5,6},{7,8,9},{10,0,11}};//10과 11은 그냥 *,#이라고 생각하시면됨
vector<int> dp[12][12];
void dijkstra(int sy,int sx){
priority_queue<tuple<int,int,int>> pq;
vector<int> dist(12,1e8);
pq.push({0,sy,sx});
dist[dial[sy][sx]]=1;
while(!pq.empty()){
int cnt,y,x;
tie(cnt,y,x)=pq.top();
pq.pop();
cnt = -cnt;
for(int i=0;i<8;i++){
int ny=y+dy[i];
int nx=x+dx[i];
int ncnt = cnt + (i%2==0?2:3);
if(0<=ny&&ny<4&&0<=nx&&nx<3){
if(dist[dial[ny][nx]]>ncnt){
dist[dial[ny][nx]]=ncnt;
pq.push({-ncnt,ny,nx});
}
}
}
}
for(int i=0;i<12;i++)
num[dial[sy][sx]][i]=num[i][dial[sy][sx]]=dist[i];
}
int ton(char c){
return c-'0';
}
int dfs(string &numbers,int left=4,int right=6,int idx=0){
if(idx>=numbers.size())return 0;
int &res = dp[left][right][idx];
if(res!=1e8)return res;
res = 0;
int next = ton(numbers[idx]);
if(left==next) return res = dfs(numbers,next,right,idx+1)+1;//해당위치에 있다면 반드시 해당 엄지로 누르기
if(right==next) return res = dfs(numbers,left,next,idx+1)+1;
return res = min(dfs(numbers,next,right,idx+1)+num[left][next],dfs(numbers,left,next,idx+1)+num[right][next]);
}
int solution(string numbers) {
int answer = 0;
//해당 숫자의 최단거리를 미리 구해놓고 시작
for(int i=0;i<4;i++){
for(int j=0;j<3;j++){
dijkstra(i,j);
}
}
for(int i=0;i<12;i++){
for(int j=0;j<12;j++){
dp[i][j]=vector<int>(numbers.size(),1e8);
}
}
return dfs(numbers);
}
int main()
{
cout<<solution("1756")<<endl;
cout<<solution("5123")<<endl;
}
|
cs |
궁금한점 혹은 모르는점 논리적인 오류나
어떤질문이든 댓글은 언제나 환영입니다.