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 이라는 수가 만들어진다. ​ 만들어져있는 계단 수의 앞 또는 중간에 수를 붙이려고 하면 머리도 복잡해지고 가장 중요한 문제는 만들어진 수의 중복이 발생하는 경우가 생긴다. ​ 그래서 ..