목록Algorithm/BackJoon (20)
S E P H ' S
17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀 www.acmicpc.net 풀이 시계 방향, 반시계 방향으로 원판을 회전하는 기능 인접수를 찾는 기능 평균을 구해 평균에 따라 원판의 수를 업데이트 하는 기능 회전하는 기능은 쉽게 구현해냈고 인접수를 찾아 없애는 것은 문제의 조건에 따라 인접한 수가 같으면 그 좌표값들을 Set에 Point 객체에 담아 넣었다. 그리고 인접수를 찾는 과정이 모두 끝나면 Set 담긴 객체들의 좌표에 해당하는 곳을 0으로 업데이트 해준 다음 평균값에 따라 계산을 해준 다음 원판의 모든 수의 합을..
10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 풀이 (구간 합) 문제를 보자마자 풀이가 바로 떠올랐는데 골드 3이라는 난이도와 입력값들의 범위가 맘에 걸리긴 했지만 생각난 풀이로 풀어보기로 했다. 구간합 배열하나를 만든 후 i, j 범위 사이의 모든 구간합들의 차이를 구해서 그 값이 3이면 cnt를 늘리는 식으로 했는데 역시나 시간초과가 났다. 먼저 나눠져야 하는 M을 범위로 하는 배열에 구간합을 M으로 나눈 값의 개수를 담는다. 이때, 나머지가 0이면 나누어 ..
10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 풀이 (이분 탐색) 단순하게 이분 탐색으로 풀어보려 했더니 중복된 숫자들이 있었다. 그래서 탐색을 할 정렬된 배열에서 찾고자 하는 수가 처음 등장하는 곳과 끝의 길이를 내면 되지 않을까 생각했다. 즉 하한(Lower Bound)값과 상한(Upper Bound)값을 찾으면 되는 것이다. 이분 탐색을 통해 처음 찾고자 하는 곳을 찾고 다시 한번 이분 탐색을 통해 찾고자 하는 값이 마지막으로 나오는 곳을 찾고 상한값에서 하한값을 빼면 ..
10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 풀이 Java 풀이 와 동일하게 이분 탐색을 사용하였다. 정말 입출력하는데에 있어서 파이썬으로 코드 작성하는 것이 편리하기는 하다. import sys input = sys.stdin.readline n = int(input()) card = list(map(int, input().split())) m = int(input()) arr = list(map(int, input().split())) card.sort() def searc..