[ 백준 12100 : 2048(Easy) ]
2048이라는 게임을 구현하면된다.
구슬 탈출2 와 비슷하게 풀면되는데 다른 점은 무조건 한쪽으로 밀어낸뒤 같은 숫자들을 합쳐줘야한다는점?
주의할점은 구슬탈출2와 다르게 현재 맵의 상태를 저장할 변수가 한개 필요하다. 사실 백트레킹으로 계속 수정해줄수도 있겠지만 너무 복잡할 것같다.
나는 그냥 변수 한개를 둔 후 복사해주고 리턴될때는 다시 돌려주고 이런 방식으로 하는것이 간단하다고 생각했다.
먼저 sol(int idx) 함수는 2048의 숫자들을 합치는 함수고, boot(int dir)함수는 이동시키는 함수다.
로직은
boot() -> 이동 -> boot -> sol(idx+1) -> ..반복 -> idx가 5이상이면 종료.
이렇게 된다.
그럼 예제를 보자.
2 2 2 2 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
4 4 4 2 2 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
이렇게 만들어져있다면 왼쪽으로 기울였을때 변하는 과정은
boot()
2 2 2 2 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
4 4 4 2 2 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
합치기
4 0 4 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
8 0 4 4 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
boot()
4 4 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
8 4 4 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
idx+1
반복
문제에 나와있듯이 한 번 합쳐진 숫자는 다시 반복해서 합쳐지지 않는다. 그러므로 5행의 8 0 4 4 는 boot에서 단순하게 8 4 4 로 이동된다. 4가 합쳐지지 않는다.
이런식으로 구현해버리면 너무 쉽게 풀리고 답을 idx가 5일때 갱신하지 않고 계속 합칠때마다 갱신시켜주면 더 빠르게 돌릴 수 있다고 생각했다.
이 블로그 검색
피드 구독하기:
댓글 (Atom)
-
[ 백준 1024 : 수열의 합 ] 간만에 푼 백준~ 쉬운 문제라고 생각하고 풀었는데 계속 틀려서 봤더니 예외 처리를 한 개 안해준것이 있었다. 만약 이 글을 보기전에 풀었을때 채점이 60%에서 자꾸 틀린다면 90%확률로 나와 같은 실수를 ...
-
[백준 1091 : 카드 섞기 ] 이 문제도 5달 전에 풀었다가 포기했었던 문제였나보다. 오늘 틀렸던 문제 다시풀기 중 풀게 되었다. 문제를 읽는데 헷갈려서 머리카락 한 10번은 쥐어짠듯. 아마 전에 풀었을때는 P배열이 각 카드가 최후에 ...
-
아마 나와 비슷한 나이대의 학생들은 대부분 대학에서 수업을 들으면서 꾸준하게 들었을 것 같다. 물론 내가 그래서 그렇다. 4차산업~ IT의 시대~ 빅데이터~ 데이터 마이닝~ 하지만 컴퓨터 관련 전공자가 아니고 더군다나 공학 계열 전공자가 아니라...
[백준 16236] 아기 상어
[ 백준 16236 : 아기 상어 ] 2018 삼성전자 sw직무 하반기 기출문제입니다. 역대 삼성전자 기출문제가 그렇듯 역시나 BFS,DFS,완탐,DP,단순구현 입니다. 저는 문제를 단순히 BFS로 풀어갔습니다. 조건만 잘 지킨다면 한번에 ...
댓글 없음:
댓글 쓰기