기본적으로 쓰는 스크립트 ahk
카테고리 없음 2022. 7. 12. 08:07
내 삶에 필수
SCV 자원 채취문제 역추적컴퓨터 이야기/Algorithm 2016. 8. 27. 22:02프로그램 명: scv 제한시간: 1 초 N * N 크기의 맵이 있다. 이 맵에는 미네랄이 군데군데 매장되어 있어서 당신은 SCV 를 이용해 이 미네랄을 채취하려고 한다. SCV 는 (1,1) 의 위치에서 출발하여 (N,N)까지 이동하는데, 이 SCV 는 고물이라 오른쪽 또는 아래쪽으로 밖에 움직이지 못한다. 이 SCV 는 무한한 양의 미네랄을 가지고 있을 수 있다고 가정하자. 이 SCV 를 이용해서 최대한 많이 미네랄을 얻도록 하는 프로그램을 작성하시오. 입력 방법
출력 방법SCV 가 채취할 수 있는 최대 미네랄 양을 출력한다.입출력 예입력 5 0 1 0 0 1 0 0 1 0 0 1 0 1 1 0 1 1 0 1 0 1 0 0 0 1 출력 6 보면 result[i][j] = arr[i][j] + result[i - 1][j]; 이러한 부분이 있는데 그냥 [i][j] 이전에 어디서 왔는가 관점으로 바라보면 i, j 는 i-1, j 으로부터 온건데 저장하기를 pair<int, int>path[102][102]; 로 잡고 path[i][j] = make_pair(i-1, j); 순서대로 넣은 후에 위와 같은 코드로 역으로 출력하면 된다. |