본문 바로가기
반응형

PS/백준

 (318)
[BOJ] 백준 11399 ATM (Swift) 문제 https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 풀이 오름차순으로 정렬을 해주어야, 뒷사람이 기다리는 시간이 줄기 때문에 시간의 합을 최소로 만들 수 있습니다. 문제 설명을 보면 힌트를 얻을 수 있습니다. 오름차순으로 정렬을 하고, 시간의 합을 누적하고, 누적된 시간의 합을 계속해서 더해주어 출력해주면 끝입니다. 소스코드 후기 오름차순으로 정렬만 해주면 쉽게 풀 수 있는 문제였습니다.
[BOJ] 백준 1931 회의실 배정 (Swift) 문제 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 풀이 회의가 빨리 시작한다고 해서 빨리 끝나지 않기 때문에 회의가 끝나는 시간에 초점을 맞춰주어야 하는 문제입니다. 하지만 끝나는 시간이 동일하다면 시작 시간이 빠른 것이 더 유리할 것입니다. (3, 3), (2, 3) 이란 회의 정보가 있다면 (2, 3) 회의를 하면 (3, 3) 회의도 진행이 가능합니다. 하지만 (3, 3) 회의를 먼저하면 (2, 3) 회의를 할 수 없습니다. 따라서 회의의 정보를 끝나는 시간에 맞춰 정렬을 하되, 끝나는 시간이 같다면 시작 시간이 더 빠른 순으로 정렬을 해줍시다. 그 이..
[BOJ] 백준 11047 동전 0 (Swift) 문제 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 풀이 그리디 알고리즘을 사용하여 풀이할 수 있습니다. K가 0이 될 때 까지, K를 가장 큰 동전부터 나눈 몫을 더해주면 동전의 최소 개수를 구할 수 있습니다. 문제의 조건 중 (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) 라는 조건이 있기 때문에, 그리디 알고리즘이 성립하게 됩..
[BOJ] 백준 25682 체스판 다시 칠하기 2 (Swift) 문제 https://www.acmicpc.net/problem/25682 25682번: 체스판 다시 칠하기 2 첫째 줄에 정수 N, M, K가 주어진다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 풀이 2차원 배열의 누적 합을 사용하여 풀이할 수 있습니다. M * N 보드를 올바른 체스판과 비교하여 다르다면 1로, 같다면 0으로 2차원 배열을 만들어 줍시다. 그 이후 만들어준 2차원 배열의 누적 합을 구하면, 올바른 체스판과 다른 것의 갯수를 알 수 있습니다. 2차원 배열의 K * K 범위 안의 누적 합 중 가장 작은 값을 출력해주면 됩니다. 소스코드 후기 2차원 배열의 누적합 알고리즘을 이런 방식으로 활용할 수 있다는 것을..
[BOJ] 백준 11660 구간 합 구하기 5 (Swift) 문제 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 풀이 2차원 배열의 구간 합을 구하는 문제입니다. 구간 합을 한 번 구해볼까요? 다음 수는 1 + 2 + 2 + 3 으로 8을 채워줘야 합니다. 채울 수의 위, 왼쪽을 보면 3으로 구간합이 이미 채워져 있습니다. 이 두 수의 3은 1 + 2, 1 + 2 로 채워져 있는데, 1이 중복되고 있습니다. 따라서 중복된 1을 빼주어야 합니다. 3 + 3 - ..
[BOJ] 백준 10986 나머지 합 (Swift) 문제 https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 풀이 누적 합을 응용하는 문제입니다. 하나씩 전부 확인해서 구한다면 $O(n^2)$의 시간복잡도가 들 것입니다. 먼저 누적 합을 구해줍시다. 구한 누적합 배열을 array라고 칭하겠습니다. 그렇다면 (i, j) 구간의 합이 m으로 나누어 떨어지는지 확인하는 과정은 $(array[j] - array[i - 1]) mod m == 0$ 인 경우 겠..
[BOJ] 백준 16139 인간-컴퓨터 상호작용 (Swift) 문제 https://www.acmicpc.net/problem/16139 16139번: 인간-컴퓨터 상호작용 첫 줄에 문자열 $S$가 주어진다. 문자열의 길이는 $200,000$자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 $q$가 주어지며, 문제의 수는 $1\leq q\leq 200,000$을 만족한다. 세 번째 www.acmicpc.net 풀이 누적 합을 사용하여 풀이할 수 있습니다. 저는 문자의 갯수가 나오는 누적합을 구하기 위해 Dictionary를 Array로 감싸주었습니다. "mandos" 라는 문자열이 있다면, array[0] = ["m": 1] array[1] = ["m": 1, "a": 1] 과 같은 형태로 만들어 주었습니다. 그 이후 누적 합을 구하는 것 처럼, ..
[BOJ] 백준 2559 수열 (Swift) 문제 https://www.acmicpc.net/problem/2559 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 풀이 누적 합을 사용해서 풀이할 수 있습니다. 구간이 고정되어 있기 때문에, 슬라이딩 윈도우를 사용해서도 풀이할 수 있습니다. 구간의 크기가 k이고 누적 합을 사용하면, 누적합 배열의 array[i + k] - array[i]로 구간의 온도의 합을 구할 수 있습니다. 슬라이딩 윈도우를 사용하면, 초기의 합은 array[0] ~ array[k - 1] 합이 될 것이고, 이 합에서 ..
반응형

티스토리툴바