문제 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제 풀이 계단 아래 시작점부터 꼭대기에 위치한 도착점까지 도착하고자 한다. 각 계단에는 획득할 수 있는 점수가 있으며, 계단을 밟을 수 있는 규칙이 존재한다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안된다. 마지막 도착 계단은 반드시 밟아야 한다. 따라서 이 문제는 경우의 수를 뻗어 가능한 경우 중 가장 큰 수를 찾는 문제와 같다. 계단의 개수가 300개 이하이므로 `DFS`로 풀게 될 경우 당연히 시간 초과가..
문제 16637번: 괄호 추가하기 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 www.acmicpc.net 문제 풀이 수식이 주어질 때, 괄호를 추가하여 최대가 되는 수를 반환하는 문제이다. 괄호를 추가하기 위해서는 2가지 방법이 있을 수 있다. 예를 들어 예제 입력 1의 경우 `3 + 8 * 7 - 9 * 2`를 괄호를 추가할 수 있는 경우를 `DFS`로 탐색하는 방법은 다음과 같다. 두수 사이에 하나의 연산자 기호가 있어야 한다. `(3 + 8) * 7 - 9 * 2`와 같이 가장 앞의 연산자부터 우선 처리한다. `3 + (8 * 7) - 9 ..
프로그래머스: 등굣길
문제 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 문제 풀이 집에서 학교까지 가는 길은 MxN 일 때, 폭우로 인해 갈 수 없는 길이 있다. 이때, 등교를 할 수 있는 경우의 수를 반환하는 문제이다. 문제는 x, y에 따른 2차원 배열을 생성하여 방문하는 경로를 기록하는 방식으로 풀 수 있다. 기존의 그래프에서 위의 그림과 같이 0을 추가한 DP 배열을 초기화한다. 그리고 처음 출발점인 집을 1로 초기화한 후 점화식인 `dp[x][y] = dp[x - 1][y] + dp[x][y - 1]`을 각..
문제 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 문제 풀이 NxN 격자판에서 파이프를 한쪽 끝 (N, N)으로 이동시키는 방법의 수를 출력하는 문제이다. 파이프는 가로, 세로, 대각선으로 움직일 수 있으며 움직이는 각도는 45도이다. 즉 가로에서 세로, 세로에서 가로는 즉시 변환할 수 없다. 경우의 수를 계산하기 위해 아래와 같이 `DFS`로 풀었다. from sys import stdin def visitable(x, y, direction): if direction == DIA..
