Jutudy

https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net [풀이] ​ ​ 기본적인 BFS 문제라고 생각하고 접근했다. 단순히 아래, 대각선 아래, 오른쪽 방향으로만 이동하기 때문에 visit 체크를 따로 해줄 필요도 없었고, (N,N) 까지 갈 수 있는 모든 경로를 구하기만 하면 되서 BFS를 돌며 파이프 앞부분이 (N,N)에 도달할 때 마다 count를 ++해주었다. 결과는 잘 나왔지만, 시간초과가 났다. ​ ​ < 동적 프로..

https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net [풀이] ​ DP문제. ​ 길이를 1부터 N까지 1씩 늘리면서 만들어진 계단 수의 맨 뒤에 숫자를 추가해주는 방법으로 경우의 수를 구해준다. ​ ex) N=10일 때 계단 수는 9876543210 이다. 여기서 N=11인 계단수를 구할 때는 9876543210 의 맨 뒤 수인 0과 1 차이나는 1을 추가해준다. 그러면 98765432101 이라는 수가 만들어진다. ​ 만들어져있는 계단 수의 앞 또는 중간에 수를 붙이려고 하면 머리도 복잡해지고 가장 중요한 문제는 만들어진 수의 중복이 발생하는 경우가 생긴다. ​ 그래서 ..

https://www.acmicpc.net/problem/10164 10164번: 격자상의 경로 입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으 www.acmicpc.net [풀이] ​ DP로 풀면 되는 문제인데, O표시를 한 부분을 기준으로 생각하면 된다. ​ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 위의 배열에서 8번에 O 표시가 되어 있으므로 1번에서 8번까지 가는 경로의 수 ( A ) 와 8번에서 15번까지 가는 경로 ( B ) 를 구한 후 곱해주면 된다. ​ 총 경로의 수 = A * B [소스코드]..