KOSTA DAY16
Algorism
kosta 예제
문제
고전게임을 잘하기로 소문난 두 형제 종현이와 종원이는 요새 갤러그라는 게임에푹 빠져 있다.
현재 종현이와 종원이의 점수는 각각 A점과 B점이고, 종현이의 점수는 A는 종원이의 점수 B보다 높거나 같다.
조현이는 매주 점수가 2배씩 상승하지만, 노력파인 종원이는 종현이를 이기기 위해 쉬지 않고 연습한 결과 매일 점수가 3배씩 상승하는 능력을 갖추었다.
이때 며칠이 지나야 종원이가 종현이의 점수보다 높아질 수 있을까?
[입력]
첫 번째 줄에 테스트케이스의 수 T(1<= T<=50)가 주어진다. 각 테스트케이스마다 최초 종현이의 점수 A와 종원이의 점수 B가 각각 공백을 두고 주어진다. 단 최초 종현이의 점수 A는 종원잉의 점수 B보다 크거나 같으면 1점 이상 5천점 이하의 점수이다. (A>=B, 1<=B<=5000)
[출력]
각 줄마다 “#T”(T는 테스트케이스 번호)를 출력한 뒤, 종원이의 점수가 종현이의 점수를
추월하게 되는데 필요한 일수를 출력한다.
[sample input]
- 4
- 7 / 1
- 8 / 3
- 4 / 4
- 4500 / 2
[sample output]
- 1 / 5
- 2 / 3
- 3 / 1
- 4 / 20
작성답안
DFS(깊이우선탐색) 알고리즘
루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법
- 구현방법
- 순환 호출(재귀함수)
- 명시적인 스택 사용
- BFS(너비우선탐색)보다 좀 더 간단하다.
- 단순검색 속도 자체는 BFS에 비해서 느리다.
- 모든 노드를 방문하고자 하는경우에 이방법을 선택
예제
문제
1번부터 N번까지 번호가 매겨져 있는 도시가 있고, 도시를 사이에 길이 있는 경우에만 이동할 수 있다.
여행을 좋아하는 종민이는 M번 도시에서 출발하여 출발지를 제외한 모든 도시를 정확히 한 번씩만 방문한 후 처음 출발지인 M번 도시로 돌아오려 한다.
이때 도시들 사이의 길을 지날갈 때 지불해야 하는 통행료가 있어,종민이는 최소한의 비용으로 모든 도시를 여행하고 싶다.
종민이가 모든 도시를여행할 때 필요한 최소비용을 출력하는 프로그램을 작성하시오.
[입력]
첫 번째 줄에 테스트케이스의 수 T(1<= T <= 10)가 주어진다.
각 테스트케이스 마다 첫 번째 줄에는 도시의 수 N과 출발지 M이 공백을 두고 주어진다.
(3<=N<=10, 1<=M<=N) 다음 N개의 줄에는 각 줄에 N개의 숫자들이 공백을 두고 주어지는데 i번째 줄의 j번째 숫자는 i번째 도시에서 j번째 도시로 가는 드는
통행료 MAT[i][j]를 의미한다.
만약 통행료가 0인 경우는 i도시에서 j도시로 가는 길이없음을 의미하다. (0<=MAT[i][j]<=50)
[제한조건]
- 도시를 잇는 도로는 일방통해이다. 심지어 i번째 도시에서 j번째 도시로 가는 길은 있어도, j번째 도시에서 i번째 도시로 가는 길은 없을 수도 있다.
- 모든 도시를 정확히 한 번씩만 지나야 함에 유의하라.
[출력]
각 줄마다 “#T(T는 테스트케이스 번호)를 출력한 뒤, 종민이가 M번 도시부터 시작하여 모든 도시를 정확히 한 번씩 순회하고 오는데 드는 통행료 최소값을 출력하시오.
(단 불가능할 경우 -1을 출력한다.)
[sample]
3
3 1
0 1 1
1 0 10
2 20 0
4 3
0 8 13 30
5 0 6 20
6 11 0 21
7 7 6 0
5 5
0 17 0 3 0
1 0 3 4 5
0 5 0 2 5
44 10 0 0 0
9 3 9 7 0
[sampe output]
1 13
2 40
3 30
강사님 해답
못풀었다.. 강사님 작성 답안은 아래와 같다.
