알고리즘12 [파이썬][백준21318] 피아노 체조 문제링크 21318번: 피아노 체조 피아노를 사랑하는 시은이는 매일 아침 피아노 체조를 한다. 시은이는 N개의 악보를 가지고 있으며, 1번부터 N번까지의 번호로 부른다. 각 악보는 1 이상 109 이하의 정수로 표현되는 난이도를 www.acmicpc.net 문제 문제풀이 x, y의 구간에서 주어진 난이도(arr) arr[i] > arr[i+1] 개수를 찾는 문제. 모든 주어진 질문을 완전 탐색으로 하면 시간초과가 났습니다. 구간을 검색해봤던 곳을 또 검색하는 경우가 있을 거라고 생각해서 누적합을 이용하면 된다고 생각했다. 난이도 배열을 한번 돌면서 전 난이도랑 비교하고 누적합을 더해주었다 따라서, dp[y] - dp[x]가 정답이 된다. 파이썬 코드 import sys """ 피아노 체조 https://.. 2022. 1. 13. 백준 14674. 영우는 사기꾼? 문제 14676번: 영우는 사기꾼? 프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 건물 종류의 개수 N, 건물 사이 관계의 개수 M, 영우의 게임 정보의 개수 K가 주어진다.(1 ≤ N, M, K ≤ 100,000) 다음 줄부터 M줄에 걸쳐 www.acmicpc.net 문제풀이 건물을 짓는데 순서가 필요하기 때문에 위상정렬을 사용하였습니다. 명령어가 1일 경우 것물을 짓을 수 있는지 indegree배열을 확인하여 체크 하였습니다. 명령어가 2일 경우 build 배열을 확인하여 0이하면 파괴할 수 없으므로 Lier!출력 아니면 1을 감소 시킵니다. 소스코드(Java) baek/baek14676.java · master · kastori / algo GitLab.com gitlab.com 더보기.. 2021. 12. 25. 백준 1863. 스카이라인 쉬운거 문제 1863번: 스카이라인 쉬운거 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 50,000) 다음 n개의 줄에는 왼쪽부터 스카이라인을 보아 갈 때 스카이라인의 고도가 바뀌는 지점의 좌표 x와 y가 주어진다. (1 ≤ x ≤ 1,000,000. 0 ≤ y ≤ 500,000) 첫 www.acmicpc.net 문제풀이 배열을 사용해서 풀려고 했었는데, 차례대로 넣으면서 높이(y좌표)가 달라질 때 처리를 하면 되겠다고 생각을 해서 스택을 사용하였습니다. 높이가 점점 증가하다가 갑자기 감소했을 때, while을 돌면서 stack의 가장 위쪽에 위치한 높이가 현재 높이보다 같거나 작아질 때까지 pop 한다. 마지막 스택에 남아있는 높이들을 pop 하면서 높이가 0이 아니면 건물의 수를 더해 준다. 소스코드(Java.. 2021. 12. 24. 백준 18116. 로봇 조립 문제 https://www.acmicpc.net/problem/18116 18116번: 로봇 조립 성규는 로봇을 조립해야 한다. 상자 안에는 여러 로봇의 부품들이 섞여 있다. 그런데 어떤 부품이 어느 로봇의 부품인지 표시가 되어있지 않다. 호재는 전자과라서 두 부품을 보면 같은 로봇의 www.acmicpc.net 더보기 문제 풀이 Union-Find를 이용해서 서로 다른 부품을 하나의 집합으로 만들어 준다. 군집끼리 union 할 때 부모에게 자식의 부품의 수를 합한다. N은 명령어의 수이지 부품의 번호 범위가 아니다. 소스코드(Java) 더보기 package baek; import java.io.BufferedReader; import java.io.InputStreamReader; import jav.. 2021. 12. 23. 이전 1 2 3 다음
