이번 문제는 으딘가에서 나왔을법한 숨바꼭질 5입니다
수빈이가 이동할수있는곳을 다 찍어두고
동생을 이동시키면서 시간의 최소값을 찾아보는 방식입니다.
특이점은 수빈이를 이동시킬때
oldTime[2][500000] 으로 맵을 만들고 (풀이에서는 500004로 정해놨음 )
홀수일때 짝수일대로 나눕니다. 그이유는
홀수는 홀수끼리 2씩 차이가나죠? 1 - 3 - 5 - 7
근데 수빈이는 2턴을 지나게되면 제자리로 올수있는 기능이있습니다.
따라서 최소시간동안 동생이 지나갈곳에 도착을 하여서 대기를 하고있으면 동생은 알아서 찾아온다 이말입니다.
하지만 수빈이가 짝수시간에 도착을 한곳에 동생이 홀수시간에 도착을하면 절대로 만날수가없겠죠? (바로옆칸인데 못만나는 슬픔 ㅜ )
그래서 짝수시간에 도착했을때랑 홀수시간에 도착했을때 , 이두가지를 저장하기위하여 2줄짜리 배열을 만들어줍니다.
처음에 맵을 -1로 초기화시킨뒤에
초기 수빈이의 위치를 0 으로 놔줍니다. ( 초기 위치가 0이기때문에 맵자체를 0으로 해두면 오류나서 -1로함)
그리고 이제 이동하면서 -1인경우 숫자를채워줍니다 bfs기때문에 작은숫자부터 차근차근 잘들어가겠죠?
수빈이가 홀수타임때, 수빈이가 짝수타임때 위치에 시간을 저장해줍니다.
그리고 동생을 돌리면서
동생의 현재 시간보다 작은값이 들어있으면 ( -1은 제외시킴)
그때 시간을 따로 저장해둡니다.
그리고 계속 찾아갑니다.뒤에 그 시간보다 짧은시간에 만난 친구가 있을수도있으니
그리고 마지막에 그 최소값을 출력해주면됩니다.
물론 처음 시간인 500004 에서 하나도 안바뀌었으면 만나지않는거니까 -1을 출력해줍니다
코드는개판이지만
제가 찾았을때 딴데 없길래..ㅎ...
그럼 2만
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 | #define _CRT_SECURE_NOWARNINGS #include <iostream> #include <queue> #include <cmath> using namespace std; queue<pair<int, int>> myq; int oldTime[2][500004] = { 0, }; int oldP, youngP;//형 +-1,x2 동생 +1 +2 +3 +4 +5 int qsize, youngT = 0; int place = 0; int minT = 500004; bool isin(int a) { if (a < 0 || a>500000)return false; else return true; } void precheck(int old, int time) { if (isin(old - 1)) { if (oldTime[(time + 1) % 2][old - 1] < 0)//-1 부분 있냐 { oldTime[(time + 1) % 2][old - 1] = time + 1; myq.push(make_pair(old - 1, time + 1)); } } if (isin(old + 1)) { if (oldTime[(time + 1) % 2][old + 1] < 0 && isin(old + 1))//+1 부분 있냐 { oldTime[(time + 1) % 2][old + 1] = time + 1; myq.push(make_pair(old + 1, time + 1)); } } if (isin(old * 2)) { if (oldTime[(time + 1) % 2][old * 2] < 0 && isin(old * 2))//*2부분 있냐 { oldTime[(time + 1) % 2][old * 2] = time + 1; myq.push(make_pair(old * 2, time + 1)); } } } int main() { cin >> oldP >> youngP; for (int i = 0; i < 500004; i++) { // -1로 초기화 oldTime[0][i] = -1; oldTime[1][i] = -1; } myq.push(make_pair(oldP, 0)); //처음값넣기 oldTime[0][oldP] = 0; // 출발위치 0으로 초기화 while (!myq.empty()) { qsize = myq.size(); for (int i = 0; i < qsize; i++) { precheck(myq.front().first, myq.front().second); myq.pop(); } } place = youngP; while (place <= 500000) { //동생돌리기 if (oldTime[youngT % 2][place] > -1 && oldTime[youngT % 2][place] <= youngT) { minT = min(minT, youngT); } youngT++; place += youngT; } if (minT == 500004)cout << -1; else cout << minT; return 0; } | cs |
'재미있는공부이야기 > 알고리듬' 카테고리의 다른 글
| 백준 9019번 DSLR (0) | 2019.02.28 |
|---|---|
| 백준 14499번 주사위굴리기 (0) | 2019.02.28 |
| 백준 7569번 토마토 (0) | 2019.02.20 |
| 백준 2178번 미로찾기 (0) | 2019.02.20 |
| KMP 알고리즘 (0) | 2019.02.15 |