문제링크 : https://www.acmicpc.net/problem/14499
아이디어
- 주사위 뼈대는 그대로 놓고, 주사위에 쓰인 숫자를 이동 시키자
시간복잡도 계산
- 전체 명령에 대해 ; O(K)
- 주사위 이동 : O(4)
- 총합 : O(4K)
자료구조
- 전체 지도 : map[30][30]
- 주사위 : dice[4][3]
코드(C++)
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 66 67 68 69 70 71 72 73 74 75 76 77 78 79 | #include <iostream> using namespace std; int map[30][30]; int dice[4][3]; int dy[] = {0,0,0,-1,1}; int dx[] = {0,1,-1,0,0}; int main() { ios::sync_with_stdio(0); cin.tie(0); // 주사위 처음에 모든면이 0이 적혀있음 fill(&dice[0][0], &dice[3][3], 0); int N,M,y,x,K; cin >> N >> M >> y >> x >> K; for(int j=0; j<N; j++) { for(int i=0; i<M; i++) cin >> map[j][i]; } for(int k=0; k<K; k++) { int t; cin >> t; int ny = y + dy[t]; int nx = x + dx[t]; // 먼저 이동가능한지 먼저 확인 if(!(ny>=0 && ny<N && nx>=0 && nx < M)) continue; y = ny; x = nx; // 주사위 이동 if(t==1) { // 동쪽으로 int tmp = dice[1][0]; dice[1][0] = dice[3][1]; dice[3][1] = dice[1][2]; dice[1][2] = dice[1][1]; dice[1][1] = tmp; } else if(t==2) { // 서쪽으로 int tmp = dice[1][0]; dice[1][0] = dice[1][1]; dice[1][1] = dice[1][2]; dice[1][2] = dice[3][1]; dice[3][1] = tmp; } else if(t==3) { // 북쪽으로 int tmp = dice[0][1]; dice[0][1] = dice[1][1]; dice[1][1] = dice[2][1]; dice[2][1] = dice[3][1]; dice[3][1] = tmp; } else if(t==4) { int tmp = dice[0][1]; dice[0][1] = dice[3][1]; dice[3][1] = dice[2][1]; dice[2][1] = dice[1][1]; dice[1][1] = tmp; } // 이동한 칸이 0인경우 if(map[y][x] == 0) { map[y][x] = dice[3][1]; } else { // 아닌경우 dice[3][1] = map[y][x]; map[y][x] = 0; } cout << dice[1][1] << '\n'; } return 0; } | cs |
문제유형
- 시뮬레이션 - 주사위 굴리기
- 주사위나 큐브나, 회전해야되는 물체 있을때, 실제로 회전하는 것이 아니라 값들을 회전시킴
'알고리즘 > 백준' 카테고리의 다른 글
백준 2304 창고 다각형 (0) | 2021.03.17 |
---|---|
백준 14719 빗물 (0) | 2021.03.17 |
백준 1062 가르침 (0) | 2021.03.17 |
백준 9663 N-Queen (0) | 2021.03.16 |
백준 2293 동전 1 (0) | 2021.03.16 |