문제 링크: https://www.acmicpc.net/problem/12100
12100번: 2048 (Easy)
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.
www.acmicpc.net
문제 설명
https://play2048.co/ 여기 들어가면 게임해볼수있다.
이 게임에서 현재 화면이 주어졌을때 최대 5번 움직여서 얻을 수있는 최대 값을 구하면 된다 .
배열이 계속 이상하게 넘어가서 3일걸린듯 . ㅠ ㅠ
알고리즘
위 그림 같이 타일 이있다고했을때 왼쪽 타일을 왼쪽으로 밀면 오른쪽 타일처럼 된다 . 여기서 알고리즘을 유추해보자.
1. 왼쪽에서 1번째 인덱스 확인 -> 아무것도 없으면 continue;
2. 2번째 인덱스 확인 -> 2를 num에 저장
3. 3번째 인덱스 확인 ->2 , 그런데 num 이랑 같다 - > 더해서 new map 맨 왼쪽부터 채움(new map idx 필요)
-> num =0 초기화
4. 4번째 인덱스 확인 -> num = 4
5. 5번째 인덱스 확인 num이랑다르다 -> num을 new map idx 에 채우고 -> num = 8
6. num != 0일 때 더 이상 확인 할 인덱스가없다 -> num을 new map 에 채움
코드
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 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 | #include<iostream> #include<algorithm> using namespace std; int N; int arr[21][21]; int new_map[21][21]; int map[21][21]; int result = 0; //왼쪽으로 미는 함수 void left() { for (int i = 0; i < N; i++) { int num = 0; int idx = 0; for (int j = 0; j < N; j++) { //map[i][j] = 0 이면 continue; if (map[i][j] == 0)continue; else { //num 에 아무것도 저장되어 있지않을때 if (num == 0) num = map[i][j]; else { //num에 저장된 숫자와 현재 map 의숫자가 동일할 때 if (num == map[i][j]) { new_map[i][idx++] = num * 2; num = 0; } //num에 저장된 숫자와 현재 map 의숫자가 동일 다를때 else { new_map[i][idx++] = num; num = map[i][j]; } } } } // 마지막에 num이 0이아니면 num을 new_map 에 추가 if (num != 0) new_map[i][idx] = num; } for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { //new_map을 map 에 넣어 주고 new_map 은 0으로 초기화 map[i][j] = new_map[i][j]; new_map[i][j] = 0; } } } //오른쪽으로 미는 함수 void right() { for (int i = 0; i < N; i++) { int num = 0; int idx = N - 1; for (int j = N - 1; j >= 0; j--) { //map[i][j] = 0 이면 continue; if (map[i][j] == 0)continue; else { //num 에 아무것도 저장되어 있지않을때 if (num == 0) num = map[i][j]; else { //num에 저장된 숫자와 현재 map 의숫자가 동일할 때 if (num == map[i][j]) { new_map[i][idx--] = num * 2; num = 0; } //num에 저장된 숫자와 현재 map 의숫자가 동일 다를때 else { new_map[i][idx--] = num; num = map[i][j]; } } } } // 마지막에 num이 0이아니면 num을 new_map 에 추가 if (num != 0) new_map[i][idx] = num; } for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { //new_map을 map 에 넣어 주고 new_map 은 0으로 초기화 map[i][j] = new_map[i][j]; new_map[i][j] = 0; } } } //위쪽으로 미는 함수 void up() { for (int j = 0; j < N; j++) { int num = 0; int idx = 0; for (int i = 0; i < N; i++) { //map[i][j] = 0 이면 continue; if (map[i][j] == 0)continue; else { //num 에 아무것도 저장되어 있지않을때 if (num == 0) num = map[i][j]; else { //num에 저장된 숫자와 현재 map 의숫자가 동일할 때 if (num == map[i][j]) { new_map[idx++][j] = num * 2; num = 0; } //num에 저장된 숫자와 현재 map 의숫자가 동일 다를때 else { new_map[idx++][j] = num; num = map[i][j]; } } } } // 마지막에 num이 0이아니면 num을 new_map 에 추가 if (num != 0) new_map[idx++][j] = num; } for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { //new_map을 map 에 넣어 주고 new_map 은 0으로 초기화 map[i][j] = new_map[i][j]; new_map[i][j] = 0; } } } //아래쪽으로 미는 함수 void down() { for (int j = 0; j < N; j++) { int num = 0; int idx = N-1; for (int i = N - 1; i >=0; i--) { //map[i][j] = 0 이면 continue; if (map[i][j] == 0)continue; else { //num 에 아무것도 저장되어 있지않을때 if (num == 0) num = map[i][j]; else { //num에 저장된 숫자와 현재 map 의숫자가 동일할 때 if (num == map[i][j]) { new_map[idx--][j] = num * 2; num = 0; } //num에 저장된 숫자와 현재 map 의숫자가 동일 다를때 else { new_map[idx--][j] = num; num = map[i][j]; } } } } // 마지막에 num이 0이아니면 num을 new_map 에 추가 if (num != 0) new_map[idx--][j] = num; } for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { //new_map을 map 에 넣어 주고 new_map 은 0으로 초기화 map[i][j] = new_map[i][j]; new_map[i][j] = 0; } } } //배열에서 최대값 int check() { int num = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { num = max(num, map[i][j]); } } return num; } //재귀로 구현한 게임 void func(int cnt) { //5번까지만 if (cnt > 5)return; result = max(result, check()); //현재 보드상태를 저장할 임시 보드 int copyBoard[21][21]; //현재 보드상태 임시 저장 for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { copyBoard[i][j] = map[i][j]; } } //오른쪽으로 밀고 재귀 right(); func(cnt + 1); //보드 복구 for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { map[i][j] = copyBoard[i][j]; } } //왼쪽으로 밀고 재귀 left(); func(cnt + 1); //보드 복구 for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { map[i][j] = copyBoard[i][j]; } } //위로 밀고 재귀 up(); func(cnt + 1); //보드 복구 for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { map[i][j] = copyBoard[i][j]; } } //밑으로 밀고 재귀 down(); func(cnt + 1); //보드 복구 for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { map[i][j] = copyBoard[i][j]; } } } int main() { cin >> N; //기본 상태 삽입 for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { cin >> map[i][j]; } } func(0); cout << result; } | cs |
코드가 상당히긴데 보면 왼쪽 오른쪽 위쪽 아래쪽 으로 각각 미는 함수의 반복이다 .
'c++ > 백준' 카테고리의 다른 글
| 백준 1629번 : 곱셈 (0) | 2020.04.13 |
|---|---|
| 백준 1074번 : Z (0) | 2020.04.13 |
| 백준 1931번: 회의실 배정 (0) | 2020.04.09 |
| 백준 11000번: 강의실 배정 (0) | 2020.04.09 |
| 백준 1700번: 멀티탭 스케줄링 (0) | 2020.04.09 |
문제 링크: https://www.acmicpc.net/problem/12100
12100번: 2048 (Easy)
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.
www.acmicpc.net
문제 설명
https://play2048.co/ 여기 들어가면 게임해볼수있다.
이 게임에서 현재 화면이 주어졌을때 최대 5번 움직여서 얻을 수있는 최대 값을 구하면 된다 .
배열이 계속 이상하게 넘어가서 3일걸린듯 . ㅠ ㅠ
알고리즘
위 그림 같이 타일 이있다고했을때 왼쪽 타일을 왼쪽으로 밀면 오른쪽 타일처럼 된다 . 여기서 알고리즘을 유추해보자.
1. 왼쪽에서 1번째 인덱스 확인 -> 아무것도 없으면 continue;
2. 2번째 인덱스 확인 -> 2를 num에 저장
3. 3번째 인덱스 확인 ->2 , 그런데 num 이랑 같다 - > 더해서 new map 맨 왼쪽부터 채움(new map idx 필요)
-> num =0 초기화
4. 4번째 인덱스 확인 -> num = 4
5. 5번째 인덱스 확인 num이랑다르다 -> num을 new map idx 에 채우고 -> num = 8
6. num != 0일 때 더 이상 확인 할 인덱스가없다 -> num을 new map 에 채움
코드
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 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 | #include<iostream> #include<algorithm> using namespace std; int N; int arr[21][21]; int new_map[21][21]; int map[21][21]; int result = 0; //왼쪽으로 미는 함수 void left() { for (int i = 0; i < N; i++) { int num = 0; int idx = 0; for (int j = 0; j < N; j++) { //map[i][j] = 0 이면 continue; if (map[i][j] == 0)continue; else { //num 에 아무것도 저장되어 있지않을때 if (num == 0) num = map[i][j]; else { //num에 저장된 숫자와 현재 map 의숫자가 동일할 때 if (num == map[i][j]) { new_map[i][idx++] = num * 2; num = 0; } //num에 저장된 숫자와 현재 map 의숫자가 동일 다를때 else { new_map[i][idx++] = num; num = map[i][j]; } } } } // 마지막에 num이 0이아니면 num을 new_map 에 추가 if (num != 0) new_map[i][idx] = num; } for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { //new_map을 map 에 넣어 주고 new_map 은 0으로 초기화 map[i][j] = new_map[i][j]; new_map[i][j] = 0; } } } //오른쪽으로 미는 함수 void right() { for (int i = 0; i < N; i++) { int num = 0; int idx = N - 1; for (int j = N - 1; j >= 0; j--) { //map[i][j] = 0 이면 continue; if (map[i][j] == 0)continue; else { //num 에 아무것도 저장되어 있지않을때 if (num == 0) num = map[i][j]; else { //num에 저장된 숫자와 현재 map 의숫자가 동일할 때 if (num == map[i][j]) { new_map[i][idx--] = num * 2; num = 0; } //num에 저장된 숫자와 현재 map 의숫자가 동일 다를때 else { new_map[i][idx--] = num; num = map[i][j]; } } } } // 마지막에 num이 0이아니면 num을 new_map 에 추가 if (num != 0) new_map[i][idx] = num; } for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { //new_map을 map 에 넣어 주고 new_map 은 0으로 초기화 map[i][j] = new_map[i][j]; new_map[i][j] = 0; } } } //위쪽으로 미는 함수 void up() { for (int j = 0; j < N; j++) { int num = 0; int idx = 0; for (int i = 0; i < N; i++) { //map[i][j] = 0 이면 continue; if (map[i][j] == 0)continue; else { //num 에 아무것도 저장되어 있지않을때 if (num == 0) num = map[i][j]; else { //num에 저장된 숫자와 현재 map 의숫자가 동일할 때 if (num == map[i][j]) { new_map[idx++][j] = num * 2; num = 0; } //num에 저장된 숫자와 현재 map 의숫자가 동일 다를때 else { new_map[idx++][j] = num; num = map[i][j]; } } } } // 마지막에 num이 0이아니면 num을 new_map 에 추가 if (num != 0) new_map[idx++][j] = num; } for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { //new_map을 map 에 넣어 주고 new_map 은 0으로 초기화 map[i][j] = new_map[i][j]; new_map[i][j] = 0; } } } //아래쪽으로 미는 함수 void down() { for (int j = 0; j < N; j++) { int num = 0; int idx = N-1; for (int i = N - 1; i >=0; i--) { //map[i][j] = 0 이면 continue; if (map[i][j] == 0)continue; else { //num 에 아무것도 저장되어 있지않을때 if (num == 0) num = map[i][j]; else { //num에 저장된 숫자와 현재 map 의숫자가 동일할 때 if (num == map[i][j]) { new_map[idx--][j] = num * 2; num = 0; } //num에 저장된 숫자와 현재 map 의숫자가 동일 다를때 else { new_map[idx--][j] = num; num = map[i][j]; } } } } // 마지막에 num이 0이아니면 num을 new_map 에 추가 if (num != 0) new_map[idx--][j] = num; } for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { //new_map을 map 에 넣어 주고 new_map 은 0으로 초기화 map[i][j] = new_map[i][j]; new_map[i][j] = 0; } } } //배열에서 최대값 int check() { int num = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { num = max(num, map[i][j]); } } return num; } //재귀로 구현한 게임 void func(int cnt) { //5번까지만 if (cnt > 5)return; result = max(result, check()); //현재 보드상태를 저장할 임시 보드 int copyBoard[21][21]; //현재 보드상태 임시 저장 for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { copyBoard[i][j] = map[i][j]; } } //오른쪽으로 밀고 재귀 right(); func(cnt + 1); //보드 복구 for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { map[i][j] = copyBoard[i][j]; } } //왼쪽으로 밀고 재귀 left(); func(cnt + 1); //보드 복구 for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { map[i][j] = copyBoard[i][j]; } } //위로 밀고 재귀 up(); func(cnt + 1); //보드 복구 for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { map[i][j] = copyBoard[i][j]; } } //밑으로 밀고 재귀 down(); func(cnt + 1); //보드 복구 for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { map[i][j] = copyBoard[i][j]; } } } int main() { cin >> N; //기본 상태 삽입 for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { cin >> map[i][j]; } } func(0); cout << result; } | cs |
코드가 상당히긴데 보면 왼쪽 오른쪽 위쪽 아래쪽 으로 각각 미는 함수의 반복이다 .
'c++ > 백준' 카테고리의 다른 글
| 백준 1629번 : 곱셈 (0) | 2020.04.13 |
|---|---|
| 백준 1074번 : Z (0) | 2020.04.13 |
| 백준 1931번: 회의실 배정 (0) | 2020.04.09 |
| 백준 11000번: 강의실 배정 (0) | 2020.04.09 |
| 백준 1700번: 멀티탭 스케줄링 (0) | 2020.04.09 |
