✓

태그:

CLASS 5 ESSENTIAL

참 유명한 게임인데, 코딩으로는 어떻게 할까요…??

풀이 비스무리한거 보기

2048 게임의 보드가 주어져있을 때 5번의 움직임으로 얻을 수 있는 최대의 블럭 값을 구하는 문제입니다. 2048 게임은 NP-complete이기 때문에 일반적인 해법이 존재하지 않기 때문에 일일이 해보는 수밖에 없습니다. 그렇다면 한 번의 슬라이드에 블럭이 어떻게 합쳐지고 이동하는지를 코드로 구현해야 합니다. 아래의 방법으로 구현할 수 있을 것 같습니다.(오른쪽에 대한 방법입니다)

1. 각 줄에 대하여
   1. 줄의 맨 오른쪽 위치에 두 포인터를 위치
   2. 하나의 포인터를 왼쪽으로 움직이면서
   3. 만약 포인터1의 위치에 블럭이 존재한다면
      1. 포인터1의 블럭을 삭제, 값을 저장
      2. 포인터2의 위치의 블럭과 값이 같다면
         1. 포인터2의 위치의 블럭의 값을 2배로 증가
         2. 포인터2의 위치를 왼쪽으로 한 칸 이동
      3. 값은 다른데 포인터2가 비어있지 않다면
         1. 포인터2의 위치를 왼쪽으로 한 칸 이동
         2. 포인터2의 위치에 값을 대입
      4. 포인터2가 비어있다면
         1. 포인터2의 위치에 값을 대입

이제 각 방향에 대하여 보드를 만들고, 각 방향에 대해 최대 5번 적용한 보드를 탐색하면서 블럭의 최대값을 구하면 됩니다.

소스 코드

언어	코드	시간	비고
C++	코드(Github) / 코드(백준)	2021-03-03 22:19:57

---