본문 바로가기

Algorithm475

[파이썬] 백준 2258 : 정육점 (골드4) [파이썬] 백준 2258 : 정육점 (골드4) 2258번: 정육점 첫째 줄에 두 정수 N(1 ≤ N ≤ 100,000), M(1 ≤ M ≤ 2,147,483,647)이 주어진다. N은 덩어리의 개수를 의미하고, M은 은혜가 필요한 고기의 양이다. 다음 N개의 줄에는 각 고기 덩어리의 무게와 가격을 나 www.acmicpc.net 문제 풀이 0. 방향성 생각 특정 가격 고기를 사면 싼 고기를 모두 고를 수 있다. table[가격] = [무게1, 무게2, ...] 이런식으로 나타내서 무게 역순으로 정렬하기. 긴 배열에서 가격 연산을 줄이기 위해서 누적 합 사용. 1. 입력 from collections import defaultdict as dd import sys input = lambda : sys.st.. 2023. 12. 10.
[파이썬] 백준 2665 : 미로만들기 (골드4) [파이썬] 백준 2665 : 미로만들기 (골드4) 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 문제 풀이 방향성 생각 0이면 부수면서 부순 횟수 카운트, 1이면 그냥 이동 힙에다가 부순횟수 저장해서 push, pop 전체코드 import heapq as hq import sys input = lambda : sys.stdin.readline().rstrip() n = int(input()) arr = [list(input()) for _ in range(n)] dire = [(1,0),(0,1),(-1,0.. 2023. 12. 7.
[파이썬] 백준 17471 : 게리맨더링 (골드4) [파이썬] 백준 17471 : 게리맨더링 (골드4) 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 문제 풀이 0. 방향성 생각 combinations로 모든 경우의 수 구하기 선택한 조합 C에 대해서 BFS를 돌려서 선택한 조합 C를 모두 순회할 수 있으면 통과 선택하지 않은 집합 C에 대해서도 선택하지 않은 집합 C가 나와야 함 둘 다 가능한 경우 정답 후보로 선정 1. 입력 from collections import deque from itertools import combinations as C import sys input.. 2023. 12. 6.
[파이썬] 프로그래머스 : 지형이동 (Lv.4) [파이썬] 프로그래머스 : 지형이동 (Lv.4) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 0.방향성 생각 BFS로 영역 나누기 한 번 더 순회하면서 다른 영역으로 갈 때 필요한 최소 cost 딕셔너리에 저장 모든 영역 연결해주기 1. from collections import deque,defaultdict def solution(land,limit): n,inf = len(land),10**9 dire = [(1,0),(0,1),(-1,0),(0,-1)] visit = [[False]*n for _ in range(n)] arr = [[-1].. 2023. 12. 6.

티스토리툴바