[C++] 백준 14500번 테트로미노

브루트 포스 / 구현 문제.

모든 경우를 다 확인하는 코드를 작성하면 맞출 수 있다.

 

문제풀이

 

문제는 위와같은 경우의 수들로 나뉘어져 있다.

이 모든 경우의 수를 고려해주면 된다.

빨간색으로 칠해진 원은 시작점이 저기일때라고 가정한 것이라고 생각하면 된다.

하드코딩으로 구현한 브루트 포스(일부분)

처음에는 해당 부분을 탐색하는 것을 일일이 따로 예외로 두어서 구현해 보았는데

틀렸습니다가 나왔을 때 고려해 줄 부분을 찾기가 너무 어려웠다.

따라서 이 코드를 다 지우고 새로운 방법으로 찾았다.

 

코드를 살펴보자.

사용한 STL과 변수

우선 결과값을 매번 갱신하기 위해, max() 메서드를 사용하려고 algorithm STL을 사용했다.

그리고 위처럼 하드코딩을 하지 않게 하기위해 Direction 클래스를 만들어서 

현재 좌표에서 각 네 칸을 어떻게 더해줘야 할지 pair자료형을 사용해서 만들었다.

 

그리고 입력받는 높이와 너비를 height, width로 만들었고,

각 칸의 숫자를 입력받는 board배열로 만들었다.

 

그리고 만든 클래스로 배열을 만들었고 고려해줄 경우의 수가 총 19개이므로 19개로 만들었다.

최초에 초기화를 해주는데 위에 그림에서 빨간색 원으로 칠해진 곳에서 어떻게 좌표를 더해줘야 각 칸으로 갈 수 있는지에 대한 수들을 적어주었다. 이 때 좌표에 더해지는 수는 {y, x}순서이다.

이렇게 하면 향상된 for문을 이용해서 더 쉽게 구현할 수 있다.

 

그리고 result 변수로 매번 최대값을 갱신해서 저장해준다.

 

각 좌표에서 모든 경우의 수를 체크하는 메서드

좌표를 매개변수로 입력받고, 좌표에서 갈 수 있는 경우의 수를 고려해준다.

• 좌표는 최대 길이보다 같거나 작아야 하며, 1보다 크거나 같아야 한다.

고려하는 네 칸이 모두 이조건을 만족해야만 경우의수라고 확인할 수 있다.

 

조건을 모두 만족한다면 각 네 칸의 숫자를 모두 더해서 result값과 비교한 후 더 큰 값으로 result에 갱신해준다.

 

메인함수

메인함수에서는 높이와 너비를 입력받고, 각 칸의 숫자를 입력받는다.

후에 모든 좌표에서 경우의수를 모두 따져본다.

시간복잡도는 최악의 경우 500 * 500 = 250,000이 되므로 시간제한에 걸리지 않게 된다.

그리고 갱신한 최종 결과값을 출력한다.

 

처음에 많이 틀린 이유가, 하드코딩 된 코드를 수정하고 수정하고 반례도 찾아봐서 다 고쳤는데도 결국 맞추지 못했다.

코드를 다 지우고 위처럼 짜야 겨우 맞출 수 있엇다.

 

하드코딩은 항상 지양해야 한다.

GitHub - kimyunseok/study-record: my study-record

코드는 위에서 확인가능하다.