728x90 스택10 [python] 백준 2304 창고 다각형 https://www.acmicpc.net/problem/2304 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net 문제 해결 새로운 유형X 오목하게 들어간 부분이 없다는 것에서 최고 높이의 기둥 좌표를 알아야한다. 가장 왼쪽에서 최고 높이 좌표까지, 가장 오른쪽에서 최고 높이 좌표까지 이웃한 기둥 사이의 영역의 넓이를 계산해준다. 높이가 올라가면 앞으로 넓이가 더 커질 것이므로 타겟 높이를 설정해서 높이가 올라가면 바꿔주고 아니면 유지시킨다. CODE import sys input = sys... 2024. 3. 14. [python] 백준 28278 스택 2 https://www.acmicpc.net/problem/28278 28278번: 스택 2 첫째 줄에 명령의 수 N이 주어진다. (1 ≤ N ≤ 1,000,000) 둘째 줄부터 N개 줄에 명령이 하나씩 주어진다. 출력을 요구하는 명령은 하나 이상 주어진다. www.acmicpc.net 문제 풀이 기본적인 스택 사용에 관한 문제이다. 다만 문제는 시간이 걸릴 수 있다는 것이다. ($N\log{N}$) sys.stdin.readline으로 속도를 신경써야한다. CODE import sys input = sys.stdin.readline def solution(A:list): if A[0] ==1: stack.append(A[1]) elif A[0]==2: if len(stack)>0: print(stack... 2023. 11. 4. [python] 백준 6198 옥상 정원 꾸미기 https://www.acmicpc.net/problem/6198 6198번: 옥상 정원 꾸미기 문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으 www.acmicpc.net 문제 해결 stack 만으로 사용하기에는 시간초과가 걸려 dp를 이용함 for문을 통해 기준 빌딩을 잡은 가장 가까운 이전 빌딩부터 차례로 높이를 비교하여 더 큰 빌딩을 잡는다. 그 빌딩을 마지막으로 처음 빌딩부터 가장 긴 길이의 감소 수열 길이를 dp를 통해 저장한다. 그러면 기준 빌딩은 가장 긴 길이의 감소 수열 길이는 +1이고 그만큼의 정답이 늘어난다. 이것도 pypy3로는 통과 (p.. 2023. 4. 23. [python] 백준 2810 컵홀더 https://www.acmicpc.net/problem/2810 2810번: 컵홀더 첫째 줄에 좌석의 수 N이 주어진다. (1 ≤ N ≤ 50) 둘째 줄에는 좌석의 정보가 주어진다. www.acmicpc.net 문제 해결 컵홀더와 사람과의 일대일 대응을 만들면 된다. stack을 이용해 남는 컵홀더와 컵홀더가 없는 사람을 저장해서 대응을 맞추면 될 것이다. 대응을 못맞추는 사람을 hurdle이라는 변수를 통해 인원수를 저장한다. n에서 hurdle을 빼면 끝 CODE import sys input = sys.stdin.readline n = int(input()) seats = list(input().rstrip()) stack = [0] hurdle = 0 while seats: x = seats.p.. 2023. 3. 17. 이전 1 2 3 다음 728x90
