분류 전체보기134 [DFS] 점프 https://www.acmicpc.net/problem/1890 N * N 숫자판 A에서 개구리가 점프를 한다. 숫자판의 각 셀은 (0, 0) 에서 (n-1, n-1) 이라 한다. 개구리는 각 셀에 적혀 있는 숫자만큼 오른쪽이나 아래쪽으로 점프를 할 수 있다. 개구리는 (0, 0)에서 출발해서 (n-1, n-1)에 도착해야 한다. 정사각형 바깥으로는 점프할 수 없다. N과 A의 각 셀의 숫자가 주어졌을 때, 개구리가 출발점에도 도착점으로 이동 가능한 지를 출력하시오. Input 첫째 줄에 양의 정수 N이 주어진다. 둘째 줄부터 N개의 줄에 A의 각 행의 원소 N개가 한 줄에 하나씩 주어진다. 3 1 2 3 2 3 1 3 2 1 3 1 2 3 2 1 2 3 2 1 Output 첫째 줄에 개구리가 출발점에.. 2022. 12. 15. [DFS] 족보 우리나라에서는 부모와 자식의 관계를 1촌이라고 한다. 따라서, 할아버지와 나는 2촌이 되고, 아버지가 아닌 할아버지의 아들은 3촌이 된다. 주어진 족보에 대해서, 두 사람의 촌수를 출력하시오. 단, 주어지는 족보에서는 부모 중에 한 사람만 표시되고, 친인척이 아닌 사람은 없다고 가정해도 된다. 또한, 촌수가 1,000,000 이상인 입력은 없다고 가정해도 된다. Input 족보에 등장하는 사람은 모두 N명이고, 번호가 1번부터 N번까지 차례대로 부여되어 있다. 족보에 등장하는 부모와 자식 관계는 모두 M개이다. 첫째 줄에 양의 정수 N과 M이 주어진다. 둘째 줄에 촌수를 계산해야 하는 두 사람의 번호 P와 Q가 주어진다. (1 양방향 그래프 생성 family = [[] for _ in range(n+1).. 2022. 12. 15. [DP] 하나가 되고 싶어 어떤 정수 X를 1로 만들고자 한다. 사용할 수 있는 연산은 다음과 같은 세 가지 연산이 있다. 1. X가 3의 배수이면 3으로 나누기 2. X가 2의 배수이면 2로 나누기 3. X에서 1을 빼기 양의 정수 N이 주어졌을 때, 위와 같은 세 가지 연산을 사용해서 1을 만들기 위해 사용해야 하는 연산의 최솟값을 출력하시오. 단, 위의 방법으로 1로 만들 수 없는 경우는 존재하지 않는다고 가정해도 된다. Input 첫째 줄에 양의 정수 N이 주어진다. 1 500000->250000->125000->62500->31250->15625->15624->7812->3906->1953->651->217->216->108->54->27->9->3->1 연산 횟수: 19 2022. 12. 14. [DP] 미로 탈출 미로 A에서 출발점은 A[0][0]이며 도착점은 A[N-1][M-1]이라 하자. 미로의 각 지점 A[i][j]를 지나갈 때 해당 지점의 값을 통행세로 내야한다. 미로의 각 지점에서는 오른쪽이나 아래쪽으로만 이동이 가능하다. N*M 크기의 미로에서 내야 하는 통행세의 최소값을 출력하시오. Input 첫째 줄에 미로의 행과 열의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 각 셀의 통행세가 M개 주어진다. 3 5 1 1 1 1 1 1 2 2 2 4 1 1 4 1 1 5 3 1 2 3 4 5 6 7 8 9 1 2 3 5 2 1 Output 첫째 줄에 주어진 미로에서 내야 하는 통행세의 최솟값을 출력한다. 8 18 import sys input=sys.stdin.readline n, m = map(int.. 2022. 12. 14. 이전 1 ··· 26 27 28 29 30 31 32 ··· 34 다음
