본문 바로가기

Algorithm 💡272

[백준 1926번] 그림 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net from collections import deque n, m = map(int,input().split()) area = [list(map(int,input().split())) for _ in range(n)] visited = [[0]*m for _ in range(n)] count_list = [] dx = [-1,1,0,0] dy = [0,0,-1,1] def bfs(x,y): if visited[x][y] != 0 or area[x][y] != 1: ret.. 2023. 10. 3.
[백준 17404번] RGB거리 2 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net n = int(input()) costs = [list(map(int,input().split())) for _ in range(n)] answer = float("inf") for i in range(3): dp = [[float("inf")]*3 for _ in range(n+1)] dp[0][i] = costs[0][i] for j in range(1,n): dp[j][0] = min(dp[j-1][1],dp[j-1][2]) + .. 2023. 10. 1.
[백준 11659번] 구간 합 구하기 4 11659번: 구간 합 구하기 4첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 jwww.acmicpc.netn,m = map(int,input().split())numbers = list(map(int,input().split()))answers = []dp = [0]*(n+1)for i in range(1,n+1): dp[i] = dp[i-1] + numbers[i-1]for _ in range(m): i, j = map(int,input().split()) answers.append(dp[j]-dp[i-1])for answer in.. 2023. 10. 1.
[백준 2579번] 계단 오르기 이번 문제는 연속으로 3칸을 밟을 수 없고 한번에 1칸이나 2칸씩 계단을 오를 수 있다는 가정 하에, 마지막 도착 계단까지 도착하는데 얻을 수 있는 총 점수의 최댓값을 구하는 문제이다. 먼저 이 문제는 완전탐색으로 풀 경우에는 N이 최대 300이기 때문에 2^300 의 경우의 수로 인해 시간초과가 발생하게 된다. 따라서 O(n) 시간복잡도로 풀 수 있는 DP 알고리즘을 사용해야 한다. 처음에 이 문제를 풀이했을 때는 dp 테이블을 1차원 배열로 선언해서 점화식을 도출하려고 했었는데, 1차원으로 선언하게 되면 점화식을 세우고 싶어도 연속한 세 계단을 모두 밟아서는 안 된다는 제약 조건을 점화식에 넣을 방법이 없다.(연속해서 몇 개의 계단을 밟았는지 확인할 수 없음) 따라서 i번째 계단까지 밟았을 때의 총 .. 2023. 10. 1.
[백준 23889번] 돌 굴러가유 23889번: 돌 굴러가유 $M$번째 줄에 걸쳐 가장 많은 모래성을 지키기 위해 벽을 설치해야 할 마을의 위치를 오름차순으로 출력한다. 가장 많은 모래성을 지킬 수 있는 경우가 두 가지 이상 존재할 경우, 사전순으로 가 www.acmicpc.net from itertools import combinations n,m,k = map(int,input().split()) # i번째 마을의 모래성의 개수 xi house_count = [0]+list(map(int,input().split())) # 돌이 굴러가기 시작하는 마을의 위치 rock_locations = list(map(int,input().split())) house_status = [True]*(n+1) # 벽의 개수 m개의 줄에 걸쳐 가장 많은.. 2023. 9. 30.
[백준 1986번] 체스 1986번: 체스 첫째 줄에는 체스 판의 크기 n과 m이 주어진다. (1 ≤ n, m ≤ 1000) 그리고 둘째 줄에는 Queen의 개수와 그 개수만큼의 Queen의 위치가 입력된다. 그리고 마찬가지로 셋째 줄에는 Knight의 개수와 위치, www.acmicpc.net n, m = map(int,input().split()) # Knight, Queen, Pawn의 개수는 각각 100을 넘지 않는 음이 아닌 정수 queen_list = list(map(int,input().split())) knight_list = list(map(int,input().split())) pawn_list = list(map(int,input().split())) # Queen은 가로,세로,대각선으로 이동 가능 / 장애물.. 2023. 9. 30.

티스토리툴바