알고리즘/백준 문제풀이

문제 https://www.acmicpc.net/problem/20005 20005번: 보스몬스터 전리품 입력의 첫째 줄에는 멤멤월드의 지도의 크기를 나타내는 두 정수 M(6 ≤ M ≤ 1000), N(6 ≤ N ≤ 1000)과 플레이어의 수 P(1 ≤ P ≤ 26)가 주어진다. M은 지도의 세로 길이, N은 지도의 가로 길이이다. 입 www.acmicpc.net 문제 풀이 맵이 작아서 그냥 바로 bfs로 같은 거리에 있는 player의 dps 묶고, 매 depth 마다 보스 때려 hp -= accm_dps 코드 import sys input = sys.stdin.readline import collections ## 입력 M, N, P = map(int,input().split()) MAP = [] f..

문제 https://www.acmicpc.net/problem/2045 2045번: 마방진 3 by 3 크기의 마방진을 생각하자. 마방진이란 가로, 세로, 대각선 위의 수들의 합이 모두 같은 성질을 가지고 있다. 몇 가지 마방진을 예로 들면 다음과 같다. 생일빵을 맞은 정신을 잃은 동주와 www.acmicpc.net 문제 풀이 지저분하지만 단순 구현.. 코드 import sys input = sys.stdin.readline ''' 마방진 : 가로, 세로, 대각선 위의 수들의 합이 모두 같다 주어진 마방진을 가로, 세로, 대각선 조사하여 합이 되는 수를 구함 마방진을 계속 가로, 세로, 대각선으로 탐색하며 0을 지움. 예외 케이스) 0 9 9 9 0 9 9 9 0 ''' MAP = [list(map(in..

문제 https://www.acmicpc.net/problem/2792 2792번: 보석 상자 보석 공장에서 보석 상자를 유치원에 기증했다. 각각의 보석은 M가지 서로 다른 색상 중 한 색상이다. 원장 선생님은 모든 보석을 N명의 학생들에게 나누어 주려고 한다. 이때, 보석을 받지 못하 www.acmicpc.net 문제 풀이 가장 큰 섬을 찾는 bfs 문제 코드 import sys input = sys.stdin.readline import collections N, M = map(int,input().split()) MAP = [list(map(int,input().split())) for _ in range(N)] T = int(input().strip()) def bfs(visited, i, j):..

문제 https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 문제 풀이 0인 부분만 잘 세팅해주면 되는 bfs 문제 코드 import sys input = sys.stdin.readline import collections N, M = map(int,input().split()) MAP = [] res = [[-1 for _ in range(M)] for _ in range(N)] for i in range..

문제 https://www.acmicpc.net/problem/1743 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다 www.acmicpc.net 문제 풀이 가장 큰 섬을 찾는 bfs 문제 코드 import sys input = sys.stdin.readline import collections N, M, K = map(int, input().split()) MAP = [[0 for _ in range(M)] for _ in range(N)] for i in range(K): r, c = map..

문제 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 문제 풀이 dp 코드 import sys input = sys.stdin.readline T = int(input().strip()) p = [1,1, 1, 2, 2, 3, 4, 5, 7, 9] while len(p)

문제 https://www.acmicpc.net/problem/12099 12099번: 점심메뉴 Q개의 줄에 줄마다 각 날의 영우와 승관이가 둘 다 좋아하는 메뉴의 수, 즉 u ≤ a ≤ v 이고, x ≤ b ≤ y 인 메뉴의 수를 출력한다 www.acmicpc.net 문제 풀이 매운맛 범위를 이분탐색해서 한번 범위를 좁혀주고, 단맛의 범위를 이분탐색으로 찾기 코드 import sys input = sys.stdin.readline import bisect N, Q = map(int,(input().split())) menu = [list(map(int,input().split())) for _ in range(N)] menu.sort() spicy = list(zip(*menu))[0] sweet = ..

문제 https://www.acmicpc.net/problem/15665 15665번: N과 M (11) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 풀이 백트래킹 코드 import sys input = sys.stdin.readline N, M = map(int,input().split()) LIST = sorted(list(set(map(int,input().split())))) total = [] def back(): if len(total) == M: print(*total) return for i in range(len(..