목록새로운 방 (1)

별집사의 IT세상

NORMAL2 새로운 방

입력 조건 출력 조건 입력 출력1 3 3 2 3 2 3 2 3 2 3Case #1 2 뒤에서 연속된 0의 최대 개수일때 열린다고 했으므로 고등학교 시절 뒤에 0이 최대로 오는 문제와 같이 생각해보면 된다. 각 경비를 곱한다고 했으므로 각 경비를 소인수 분해하여 2의 개수와 3의 개수만 저장하고 마지막까지 갔을 때 두개의 페어가 최대값이 되는 경우를 찾으면 된다. 해당 문제에서는 상, 하, 좌, 우로 이동할 수 있다고 나와있지만, 최단거리로 가야된다고 했으므로 실질적으로 이동가능 한 경우는 하, 우 뿐이다. 처음에 고민했던 부분은 최대값이 각 지점까지 왔을 때 최대값과 같은 가 였는 데 이는 간단한 예로 아님을 확인 할 수 있다. 만일 3*3의 미로에서 배열 1,1로 오는 2가지 경우의 수를 예로 들어보자..
IT/코드그라운드 2017. 4. 11. 19:55
Prev 1 Next