파이프 옮기기 1 [백준 17070] - python

 

 

 

import sys
input = sys.stdin.readline

def BOJ17070() :
  N = int(input())
  graph = []
  for _ in range(N) :
    graph.append(list(map(int, input().split())))

  answer = [[[0] * N for _ in range(N)] for _ in range(N)]
  answer[0][0][1] = 1

  for x in range(0, N) :
    for y in range(2, N) :
      # 가로, 세로
      if graph[x][y] == 0 :
        answer[0][x][y] = answer[0][x][y-1] + answer[2][x][y-1]
        answer[1][x][y] = answer[1][x-1][y] + answer[2][x-1][y]
      # 대각선
      if graph[x][y] == 0 and graph[x-1][y] == 0 and graph[x][y-1] == 0 :
        answer[2][x][y] = answer[0][x-1][y-1] + answer[1][x-1][y-1] + answer[2][x-1][y-1]

  print(answer[0][N-1][N-1] + answer[1][N-1][N-1] + answer[2][N-1][N-1])

BOJ17070()

 

접근 방법 :

0. 일단 겁 먹지 말자.  문제에서 요구하는 대로 접근하면 된다

1. 맨 처음 파이프가 위치해 있는 지점은 가지수가 1이다

2. 가로, 세로, 대각선으로 움직이는 3차원 배열을 생성한다.(가로 : 0, 세로 : 1, 대각선 : 2)

3. 그래프를 순차로 탐색하자 
4. 순차시에 접근하게 되는 x,y 지점에는 가로에서 접근, 세로에서 접근, 대각선에서 접근하는 경우가 있을것이다(문제에 친절히 나와있다.)
     대각으로 접근할때는 조건이 붙게 되므로 이 조건이 아닐때만 각 케이스에서 접근하는 경우의 수를 더해주면 된다.

5. 목표 지점에 접근하게 되는 모든 가지수를 더한후 출력하자

 

장애물 이였던 것 :

0. 문제 설명만 보고 겁을 먹었다.

1. 결국 문제 분류를 보았고 dp로 접근해서 풀려 했다.

2. 결국 못 풀고 다른 분들의 풀이를 참고했다.

 

 

 

https://www.acmicpc.net/problem/17070

17070번: 파이프 옮기기 1