본문 바로가기
  • 개발하는 곰돌이

Algorithm/BOJ115

[Kotlin] 백준 1806 : 부분합 문제 링크 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 문제 해설 부분합과 투 포인터가 결합된 문제다. 부분합에 대한 내용은 아래 포스트를 참고하면 좋다. 링크 : 누적합(Prefix Sum)과 부분합(Partial Sum) with Kotlin 누적합을 저장할 크기가 \(n+1\)인 배열을 선언하고 1번째 인덱스부터 누적합을 저장해나간다. 이후 투 포인터를 사용해서 배열 위를 이동하기 시작한다. start부터 end까지의 합이 \(S\) 이상이라면 기존 구간 길이의 최소값과 현재 구간 길이.. 2022. 12. 17.
[Kotlin] 백준 25916 : 싫은데요 문제 링크 25916번: 싫은데요 $6$번째 구멍부터 $8$번째 구멍까지 막으면 총 $9$의 부피를 소모하고, 최대값인 $9$를 출력한다 www.acmicpc.net 문제 해설 부분합의 최대치 중 M 이하인 값을 구하는 문제다. 문제에 햄스터가 막을 구멍은 반드시 연속되어야 한다는 제한이 있기 때문에 투 포인터를 이용하여 풀 수 있다. 투 포인터는 이름 그대로 두 개의 점이 배열 위를 이동하면서 주어진 조건에 맞는 답을 찾아가는 방법이다. 본 문제에서는 독의 첫 번째 구멍부터 마지막 구멍까지 햄스터가 계속 몸을 늘리거나 줄여가면서 답을 찾을 수 있다. 주어진 예제를 그림으로 표현해보자. 그림을 보면 현재 햄스터가 막은 구멍 크기의 합계가 조건보다 작은 경우엔 햄스터가 오른쪽으로 늘어나고, 햄스터가 막은 .. 2022. 12. 16.
[Kotlin] 백준 11387 : 님 무기가 좀 나쁘시네여 문제 링크 11387번: 님 무기가 좀 나쁘시네여 각 줄마다 "공격력", "힘", "치명타 확률", "치명타 피해비율", "공격속도 증가"의 수치를 나타내는 다섯 개의 정수가 공백을 사이에 두고 순서대로 주어진다. 첫 번째 줄은 무기를 장착한 크리의 www.acmicpc.net 문제 해설 문제 자체는 단순한 구현 문제지만 주의할 점이 있다. 전투력을 계산할 때 실수 계산을 많이 하게 되는데 컴퓨터는 내부적으로 모든 수를 2진법으로 저장하기 때문에 소수점 이하 부분은 정확하게 저장할 수 없고 근사치를 저장하게 된다. 이 과정에서 여러번의 연산을 하다보니 오차가 발생하여 식은 맞지만 답은 틀리는 경우가 발생할 수 있다. 따라서 BigDecimal을 사용하여 오차 없이 계산해야 한다. 이점만 주의하면 크리와 .. 2022. 12. 15.
[Kotlin] 백준 12785 : 토쟁이의 등굣길 문제 링크 12785번: 토쟁이의 등굣길 인하대학교에 다니는 토쟁이는 y축과 평행한 w개의 도로, x축과 평행한 h개의 도로가 있는 도시에 살고 있다. 토쟁이의 집은 이 도시의 맨 왼쪽 아래에 위치하며 좌표로는 (1, 1)로 표시할 수 있다. www.acmicpc.net 문제 해설 최단 경로 문제다. 토쟁이의 집부터 토스트 가게까지의 최단경로와 토스트 가게부터 학교까지의 최단경로를 구하여 두 값을 곱한 결과를 1,000,007로 나눈 나머지를 출력하면 된다. 최단 경로 문제는 조합으로 해결할 수 있다. 위와 같은 모양의 지도가 있을 때 start에서 end까지 이동하는 최단 경로의 수는 →오른쪽 5개와 ↑위쪽 3개로 이루어진 집합에서 5개의 →오른쪽이나 3개의 ↑위쪽을 뽑는 경우의 수가 된다. 따라서 위.. 2022. 12. 14.
[Kotlin] 백준 26215 : 눈 치우기 문제 링크 26215번: 눈 치우기 집 2와 집 3 앞의 눈을 치우고, 집 2와 집 3 앞의 눈을 치우고, 집 1과 집 3 앞의 눈을 치운 뒤 집 3 앞의 눈을 두 번 치우면 5분만에 모든 집 앞의 눈을 치울 수 있다. www.acmicpc.net 문제 해설 정렬을 이용하여 풀 수 있는 문제다. 우선 문제의 조건에 따라 분당 치울 수 있는 눈은 한집만 1 또는 두 집에서 각각 1씩, 총 2를 치울 수 있다. 따라서 한 집 앞에 쌓인 눈의 양이 1440을 초과한다면 무슨 수를 쓰더라도 24시간 내에 치울 수 없기 때문에 -1을 출력하고 프로그램을 종료한다.(코드의 11~14번째 줄) 그 외의 경우는 각 집 앞에 눈이 쌓인 양을 내림차순으로 정렬하여 해결한다. 눈이 쌓인 양이 가장 많은 집과 두 번째로 많이.. 2022. 12. 12.
[Kotlin] 백준 15595 : 정답 비율 계산하기 문제 링크 15595번: 정답 비율 계산하기 첫째 줄에 어떤 문제의 총 제출 횟수 N(1 ≤ N ≤ 200,000)이 주어진다. 둘째 줄부터 N개의 줄에 각 제출의 정보가 제출 번호 순서대로 주어진다. 제출 정보는 총 7가지가 공백 하나로 구분되어져 있 www.acmicpc.net 문제 해설 BOJ의 정답 비율을 계산하는 알고리즘을 직접 구현해보는 문제다. 입력에 많은 정보가 있지만 문제의 조건을 봤을 때 필요한 것은 문제를 맞은 사람의 수, 문제를 맞은 사람이 이전까지 틀린 횟수, 문제를 맞은 사람의 유저 아이디만 있으면 된다. 우선 문제를 맞은 사람이 이전까지 틀린 횟수를 계산하기 위해 HashMap을 사용했다. 문제를 아무리 많이 틀려도 해당 유저 아이디가 최종적으로 문제를 맞추지 못한다면 분모에 .. 2022. 12. 10.
[Kotlin] 백준 1270 : 전쟁 - 땅따먹기 문제 링크 1270번: 전쟁 - 땅따먹기 첫째 줄에는 땅의 개수 n(n t / 2) when (strongest?.sign ?: 0) { 1.toByte() -> "-${strongest}\n" else -> "${strongest}\n" } else "SYJKGW\n") military.clear() } println(sb) } class Military(var num: UInt, var sign: Byte) { override fun toString() = "${this.num}" override fun equals(other: Any?) = this.num == (other as Military).num && this.sign == other.sign override fun hashCode() = .. 2022. 12. 9.
[Kotlin] 백준 1931 : 회의실 배정 문제 링크 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 해설 무엇을 기준으로 정렬을 할지 생각해봐야 할 문제다. 회의 시작 시간을 기준으로 정렬하면 (1, 4), (2, 3), (3, 8) 같은 경우엔 최대 2개의 회의를 할 수 있지만 정렬 기준으로 보면 1개의 회의밖에 진행할 수 없다. 그러므로 회의가 끝나는 시간을 기준으로 오름차순 정렬한다. 만약 끝나는 시간이 같은 회의가 같다면 시작하는 시간이 빠른 순서로 정렬한다. 시작 시간을 정렬하지 않으면 회의 시작 시간과 끝 시간이 같은 회의를 카운팅하지 못하는 경우가 생긴다. 예를 들어, (1, 2), (3, 3), (2, 3)이 있을 때 이 순서로 카운팅하면 (2,.. 2022. 12. 8.

티스토리툴바