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

Algorithm116

[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.
[Kotlin] 백준 2630 : 색종이 만들기 문제 링크 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 문제 해설 기본적인 분할정복 문제다. 주어진 크기에 맞는 2차원 배열을 만든 후 전체 크기부터 검사를 시작해서 색종이로 사용할 수 없으면 4등분하여 다시 검사를 한다. 검사하는 중에 색종이로 사용할 수 있는 경우(=해당 구간의 모든 요소가 같은 경우)면 해당 색상의 색종이 개수를 1 증가시키고 해당 부분은 검사를 종료한다. Code import java.util.StringTokenizer val n = readln().to.. 2022. 12. 8.
[Kotlin] 백준 11866 : 요세푸스 문제 0 문제 링크 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 문제 해설 문제의 예시를 그림으로 나타내면 다음과 같다. 그림을 보면 다음에 나갈 사람의 위치는 시작 위치 + \(k\) - 1인 것을 알 수 있다. 즉, 다음 순서로 나갈 사람의 위치는 이전에 나간 사람의 위치에 \(k-1\)을 더하면 된다. 이제 남은 사람의 수가 \(k\)보다 작아졌을 때의 처리만 하면 되는데, 이 때는 앞에서 구해진 다음 순서로 나갈 사람의 위치가 남은 사람의 수보다 작아질 때까지 남은 사람의 수를 빼주면 된다. 나간 사람의 번호는 별도의 배열에 저장하고 문제의 조건에 맞는 형태로 출력하면 된다. Code fun .. 2022. 12. 8.

티스토리툴바