https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 접근방식 dp 배열을 만들어서 dp[현재위치값] = 현재 위치값+ max(이동할 수 있는 위치 값) 으로 값을 갱신하며 최대,최솟값을 구한다. 처음 풀이 import sys input = sys.stdin.readline n = int(input()) arr = [list(map(int, input().split())) for _ in range(n)] dp_max = [[0] * 3 for _ in range..
https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 각 칸에 그 지점의 높이가 쓰여 있고, 각 지점의 이동은 상하좌우 이웃한 곳끼리만 가능하다. 제일 왼쪽 위칸에서 제일 오른쪽 아래칸으로 가는데 항상 높이가 더 낮은 지점으로만 이동하는 경우의 수를 구하자. 접근 방식 DP를 이용해 지나갈때마다 방문표시를 해 그 지점에 카운트를 시키며 지나가 마지막 경로에 도착시 1을 리턴하며 시작점 DP값에 증감시켜 경우의 수를 구한다. DFS를 이용해 상화좌우..
https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 접근 방식 같은 색상이 상하좌우로 인접한 경우에 두 글자는 같은 구역에 속한다. -> 상하좌우 리스트를 만들어서 bfs를 이용해 같은 구역을 추출한다. -> 그림 안에서 bfs로 방문표시와 함께 같은 구역을 추출해 크게 구역을 나눈다. 적록색약인 경우 그림에서 R과 G를 같게 설정한뒤 bfs를 통해 구역을 나눈다. -> 위에서 썼던 방문표시리스트를 초기화해서 bfs를 돌아 구역을 나눈다. ..