백준- 18430번 : 무기공학

doldol_kim·2020년 7월 7일
0

BOJ - 18430번 : 무기공학

전형적인 백트래킹으로 푸는 문제였다.

우선, 부메랑은 다음과 같이 4가지 모양을 가질 수 있고, 이를 최대한 많이 사용하여 최대 강도를 만들어 내야 한다.

문제 해결 방법

  1. 예를들어 첫번째 부메랑을 만들기 위해서는 가운데 (y, x)를 기준으로
    • (y,x-1)(y+1, x)가 범위 내에 있어야 한다
    • (y,x-1)(y+1, x)가 사용된 적이 없어야 한다. 나머지 부메랑들도 마찬가지이다.
  2. 부메랑이 만들어지면 오른쪽으로 한 칸 옮겨가서 다른 부메랑을 더 만든다.
    • 3개의 지점(y,x), (y,x-1), (y+1, x)을 방문체크 한다.
    • 문제의 조건에 맞게 부메랑의 강도를 구한다.
    • 오른쪽으로 한칸 움직이고, 새로 구한 부메랑의 강도를 매개변수로 넣어 재귀호출을 한다.(백트래킹)
  3. 4개의 부메랑 모양 전부 확인한다.
  4. (x == m) 이라면 오른쪽 끝까지 간 것이므로, 한 줄 밑으로 내려가고 맨 왼쪽부터 시작한
  5. (y == n) 이라면 가장 아래쪽까지 다 확인한 것이므로, 최종 부메랑 강도의 합계 중 최댓값을 구한 뒤 리턴한다.

소스코드

https://gist.github.com/midaslmg94/1601d408e82888cb60681c772d7a1a05

profile
김돌돌입니다

0개의 댓글