본문 바로가기
728x90

백준 풀이103

[백준/BOJ] - 1149번 python 풀이 - DP Key Point 1. 1번째 집은 비교 대상이 없으므로 입력받은 그대로 저장. 2. 2번째 집부터 바로 앞 집과 비교하여 색을 고를 수 있으므로 앞 집의 색 중 cost가 낮은 값을 d 배열에 넣어준다. 3. 집집 마다 경우의 수는 R, G, B 총 3가지 색을 칠할 경우이므로 각 경우 마다 누적 cost가 얼마나 드는지 저장하는 알고리즘 import sys input = sys.stdin.readline n = int(input()) d = [list(map(int, input().split())) for _ in range(n)] # 0번째 idx(1번째 집)는 확인x 1번째 idx(2번째 집)부터 최적의 값을 해당 배열에 갱신 for i in range(1, n): #0번째 idx인 1번째 집은 .. 2022. 12. 29.
[백준/BOJ] - 11726번 python 풀이 - DP Key Point 1. 점화식으로 표현 가능하여 dp로 풀면 되는 문제이다. 2. n이 3초과 값부터 점화식이 적용되므로 d[1] ~ d[3] 까지의 값은 미리 지정해준다. Problem Solving d[1] = 1 d[2] = 2 d[3] = 3 d[4] = 5 d[5] = 8 d[6] = 13 . . . d[9] = 55 규칙에서 n이 3초과 부터 d[n] = d[n-1] + d[n-2]의 값을 만족한다. import sys input = sys.stdin.readline d = [0]*1001 d[1] = 1 d[2] = 2 d[3] = 3 n = int(input()) if n>3: for i in range(4, n+1): d[i] = d[i-1] + d[i-2] print(d[n] % 100.. 2022. 12. 28.
[백준/BOJ] - 2589번 python 풀이 - BFS Key Point 1. 각 case 마다 visited의 초기값을 사용해야하기 때문에 bfs 접근할 때 마다 deepcopy 해준다. 2. 시작점의 visited 값은 1로 설정해준다.( 0으로 설정할 경우 시작점으로 다시 되돌아갈 수 있기 때문이다.) import sys import copy input = sys.stdin.readline from collections import deque n, m = map(int,input().split()) mapp = [list(map(str, input().rstrip())) for _ in range(n)] visited = [[0 for _ in range(m)] for _ in range(n)] dx, dy = (-1, 1, 0, 0), (0, 0, -.. 2022. 12. 22.
[백준/BOJ] - 7576번 python 풀이 - BFS key point 1. 기본적인 bfs 문제와 다르게 벽을 만드는 함수를 하나 더 생성해야한다. 2. 벽을 만드는 함수는 재귀 함수를 통해 벽을 만들고 bfs 함수에 접근하게 끔 구현한다. 3. 벽을 세우는 매 case마다 기존 배열이 바이러스로 뒤덮이기 때문에 bfs 함수에서 사용되는 메인 배열은 초기 배열 상태이어야 하기에 bfs 접근 할 때 마다 딥카피를 해주어야한다. 4. 바이러스 옮기는 과정을 마무리한 후 배열에 0값을 세어 그 값의 최댓값을 산출해내는 것이 마무리. 알게 된 점 def makewall(cnt): if cnt == 3: bfs() return for i in range(n): for j in range(m): if arr[i][j] == 0: arr[i][j] = 1 makewa.. 2022. 12. 22.
[백준/BOJ] - 7576번 python 풀이 - BFS Key Point 1. 배열의 값이 1인 위치에서 동서남북으로 퍼지는 매커니즘이다. 2. 처음 입력받은 배열의 값이 1인 위치들을 모두 deque에 넣어준다. 3. 완성되어있는 deque속에 담겨진 위치를 토대로 bfs 를 동작시킨다. 4. 1일차에 익은 토마토에 의해 익혀진 토마토들의 값(배열 속 값)은 몇일 차 인지를 표시하기 위해 + 1 을 해준다. 5. bfs가 마무리 된 후 2중 for문을 돌리며 0인 값이 아직도 존재할 경우 -1 출력 존재하지 않을 경우 배열에 존재하는 최댓값 -1을 출력한다. import sys from collections import deque input = sys.stdin.readline m, n = map(int, input().split()) queue = deq.. 2022. 12. 21.
[백준/BOJ] - 2178번 python 풀이 - BFS Key Point 1. 최단거리를 구하는 문제는 bfs가 적절하다. 2. 시작 노드로 부터 한 다리 건너 있는 노드들의 값을 +1 씩 더해주어 최종 노드 위치의 값을 확인한다. import sys from collections import deque input = sys.stdin.readline n, m = map(int,input().split()) # 한줄에 배열을 받을 수 있는 방법 arr = [list(map(int,input().rstrip())) for _ in range(n)] dx, dy = (-1, 1, 0, 0), (0 ,0 ,- 1, 1) def bfs(a,b): q = deque() q.append((a,b)) while q: x, y = q.popleft() for i in ra.. 2022. 12. 20.
728x90

티스토리툴바