2042. 구간 합 구하기 (Python)
2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 풀이 세그먼트 트리를 사용하는 대표적인 문제이다. 해당 문제에 대한 풀이는 세그먼트 트리에 대한 포스팅을 참고하자. 코드 import sys input = sys.stdin.readline # 세그먼트 트리 초기화 # start, end: 범위(구간), node: 세그먼트 트리에서 노드 번호 def init(start, end, node): # start와 end가 같다는 것은 leaf node임을 의미..
2022. 4. 22.
5014. 스타트링크 (Python, Swift)
5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 풀이 현재 위치에서 bfs를 통해서 목표 층인 G층에 최소 몇 번의 버튼 동작으로 이동할 수 있는지를 구할 수 있다. bfs를 수행할 때 방문 체크가 필요한데 이 문제에서는 건물의 전체 층에 대하여 현재 위치인 n층에 도착하기 위해 총 버튼을 몇 번 눌렀는지를 기록해둔다. 예를 들어, 현재 n층에 5번 버튼을 눌러 도착했는데 이전에 n층에 4번 버튼을 눌러서 도착했던 경우가 있다면 현재 이동 기록은 큐에 넣지 않는다. 하지만 현재 n층에 3번 버튼을 눌러 도착했다면 더 적은..
2022. 4. 20.
