IT Crowd

www.acmicpc.net/problem/2477 2477번: 참외밭 첫 번째 줄에 1m^2의 넓이에 자라는 참외의 개수를 나타내는 양의 정수 K (1≤K≤20)가 주어진다. 참외밭을 나타내는 육각형의 임의의 한 꼭짓점에서 출발하여 반시계방향으로 둘레를 돌면서 지나� www.acmicpc.net 입력 변의 방향이 동,서(1,2)일 경우 가로변, 변의 방향이 남,북(3,4)일 경우 세로변임을 알 수 있음. 6각형이고 입력이 순서대로 들어오므로 변의 방향과 길이를 저장하기 위한 2차원 배열을 생성하여 저장함. 문제 풀이 ㄱ자 모양이라는 것에서 아이디어를 얻음 그림과 같이 큰 사각형에서 작은 사각형을 빼면 ㄱ자 도형의 면적을 구할 수 있음 큰 사각형의 면적 주어진 변의 길이중 가장 긴 가로 변, 세로변의 길..

문제풀이 dfs를 이용하여 최적화를 하는 문제이다. 가장 높은 봉우리에서 부터 탐색을 시작함. 봉우리의 사방을 탐색 다음 길이 낮으면 그대로 탐색 진행(dfs호출) 다음 길의 높이가 같거나 높고 공사를 아직 안했으면 공사를 진행함 공사는 최대 깊이 K만큼 할 수 있음 (1~K) 모든 경우( 모든 공사깊이 ) 를 탐색 공사 후에 다음 길의 높이가 낮아졌다면 dfs를 호출해서 탐색 계속 (dfs호출) 등산로길이의 최대값을 계속 업데이트해서 최대값을 결과로 얻음 소스코드(python) dr = [-1,0,1,0] dc = [0,1,0,-1] def dfs(r,c,path,isConst): global ans if ans < path: #최장 등산로 갱신하기 ans = path #사방 탐색 : 등산로 탐색 fo..