본문 바로가기

Algorithm475

[파이썬] 백준 1234 : 크리스마스 트리 (골드2) [파이썬] 백준 1234 : 크리스마스 트리 (골드2) 1234번: 크리스마스 트리 첫째 줄에 트리의 크기 N, 빨강의 개수, 초록의 개수, 파랑의 개수가 주어진다. N은 10보다 작거나 같다. 빨강, 초록, 파랑의 개수는 0보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 문제 풀이 방향성 생각 트리 높이가 10이고 각 높이에 같은 개수로 채우는 방식이 매우 제한적이다. 하드코딩으로 높이마다 처리해주기 처음에 개수를 많이 소모해야 가지치기로 불필요한 케이스를 많이 잘라낼 수 있다. 낮은 높이부터 채워서 꼭대기로 올라간다. 만약 쌓다가 공이 부족하면 탈출. 끝까지 올라갈 수 있으면 리스트에 저장한 가짓수를 모두 곱해서 answer에 더한다. 전체코드 n,red,green,blue .. 2023. 11. 5.
[파이썬] 백준 17825 : 주사위 윷놀이 (골드2) [파이썬] 백준 17825 : 주사위 윷놀이 (골드2) 17825번: 주사위 윷놀이 첫째 줄에 주사위에서 나올 수 10개가 순서대로 주어진다. www.acmicpc.net 문제 풀이 0. 방향성 생각 완탐 4^10 == 10**6 -> 중간에 조건에 부합하지 않는 경우 탐색x -> 백트래킹 맵 구현은 그냥 인덱스 짜서 구현했음... 1. 입력 dice = list(map(int,input().split())) info = {i:[0,i+1,i+2,i+3,i+4,i+5] for i in range(33)} info[16] = [0,17,18,19,20,21] info[17] = [0,18,19,20,21,21] info[18] = [0,19,20,21,21,21] info[19] = [0,20,21,21,.. 2023. 10. 22.
[파이썬] 백준 28709 : 와일드카드 괄호 문자열 (골드1) [파이썬] 백준 28709 : 와일드카드 괄호 문자열 (골드1) 28709번: 와일드카드 괄호 문자열 각 테스트케이스마다 한 줄에 하나씩, ‘?’ 문자를 ‘(’이나 ‘)’로, ‘*’ 문자를 ‘(’, ‘)’로 이루어진 길이가 $0$ 이상인 원하는 문자열로 대체하여 $S$를 올바른 괄호 문자열로 만들 수 www.acmicpc.net 문제 풀이 0. 방향성 생각 *이 있는 케이스와 없는 케이스로 나눈다. 왜 와이 - > 입력 문자열 S를 split('*')을 통해 나누면 항상 다음의 케이스로 나누어진다. S = *A꼴 -> string = ['',A] : 왼쪽에서 '('를 무한정 공급 가능하다. 뒤에서부터 순회해서 (개수가 ?)개수랑 일치시킨다. S = A*꼴 -> string = [A,''] : 오른쪽에서 .. 2023. 10. 22.
[파이썬] 백준 18513 : 샘터 (골드4) [파이썬] 백준 18513 : 샘터 (골드4) 18513번: 샘터 첫째 줄에 자연수 N과 K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N, K ≤ 100,000) 둘째 줄에 N개의 샘터의 위치가 공백을 기준으로 구분되어 정수 형태로 주어진다. (-100,000,000 ≤ 샘터의 위치 ≤ www.acmicpc.net 문제 풀이 0. 방향성 생각 입력 범위 매우 크다 -> 자료구조? 우물과 우물 사이 공간을 2개로 분리한다. 우물 좌우에 각각 몇개의 집을 지을 수 있는지 체크 힙에 (우물로부터 가장 가까운 집, 남은 공간, 우물 좌표)를 넣는다. 1. 입력 import heapq as hq import sys input = lambda: sys.stdin.readline().rstrip() n,k = .. 2023. 10. 22.

티스토리툴바