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

수학8

[Kotlin] 백준 22941 : RPG 마스터 오명진 문제 링크 : https://www.acmicpc.net/problem/22941문제 해설주어진 조건에 따라 용사의 승리 여부를 시뮬레이션해야 합니다. 다만 시간 제한이 0.3초밖에 안되고 공격력은 최소가 \(1\)인 반면 HP는 최대 \(2^{31}-1\)이기 때문에 최악의 경우라면 \((2^{31} - 1)\times 2\)번의 연산을 수행해야 해서 시간 초과가 발생합니다. 하지만 문제에서 요구하는 답을 구하려면 용사가 쓰러지기 전에 마왕이 먼저 쓰러지는지의 여부만 확인하면 되기 때문에 단순 수학 계산만으로도 판별할 수 있습니다. 우선 마왕을 쓰러트리기 위해 필요한 용사의 공격 횟수를 구해서 소수점 이하는 올림처리 해줍니다.braveAttackCount = (devilHp + braveAtk - 1).. 2024. 11. 20.
[Kotlin] 백준 30704 : 정사각형 연결하기 문제 링크 : https://www.acmicpc.net/problem/30704문제 해설한 변의 길이가 1인 정사각형을 겹치지 않게 나란히 붙여서 둘레가 최소가 되는 다각형을 만들어야 합니다. 격자 형태의 공간에서 한 변의 길이가 1인 정사각형을 배치해서 도형을 만든다는 점에서 이 문제는 넓이가 \(N\)인 다각형 중에서 둘레가 가장 작은 다각형의 둘레를 구하는 것과 같다는 것을 알 수 있습니다. 우선 둘레를 구하기 전에 다각형이 정사각형 또는 직사각형이 아닌 경우에 대해 한번 보겠습니다.\(N\)이 5인 경우에는 위와 같이 정사각형들을 배치할 수 있습니다. 이 경우에 대해 둘레를 구할 때 살짝 비틀어 보면 아래와 같이 둘레가 구해지는 것을 볼 수 있습니다.직사각형에서 움푹 들어간 부분의 변을 바깥으로.. 2024. 10. 15.
[Kotlin] 백준 31882 : 근수 문제 링크 : https://www.acmicpc.net/problem/31882문제 해설주어진 문자열에서 연속된 2로만 이뤄진 부분 문자열(이하 근수)들을 추출하여 점수를 구해야합니다. 근수들은 문자열 전체를 순회하면서 현재 숫자가 2라면 현재까지 구해진 부분 문자열에 2를 추가하고, 그 외의 경우에는 현재까지 구해진 부분 문자열을 리스트에 추가한 후 부분 문자열을 초기화하는 방법으로 구할 수 있습니다. 문자열을 모두 순회한 후 구해놓은 부분 문자열이 있다면 리스트에 추가해줍니다.for (num in s) { if (num == '2') { sb.append(2) continue } if (sb.isEmpty()) continue list.add(sb) .. 2024. 8. 22.
[Kotlin] 백준 14715 : 전생했더니 슬라임 연구자였던 건에 대하여 (Easy) 문제 링크 : https://www.acmicpc.net/problem/14715문제 해설나름 간단한(?) 수학 문제. 별다른 알고리즘이 필요하진 않다. 슬라임은 2 이상의 에너지를 갖는 슬라임으로 계속 분할할 수 있다. 분할할 수 있는 슬라임이 존재하지 않을 때까지 슬라임을 분할한다는 것은 모든 슬라임의 에너지가 소수가 된다는 것이고, 모든 슬라임의 에너지가 소수가 되도록 분할한다는 것은 다시 말해 최초의 슬라임을 소인수분해하면 된다는 뜻이 된다. 문제에서 구해야 하는 값은 슬라임의 흠집 개수 = 슬라임을 분할한 횟수가 된다. \(K=7200\)인 경우를 생각해보자. \(K\)를 소인수분해하면 \(7200=2\times 2 \times 2 \times 2 \times 2 \times 3 \times 3.. 2024. 5. 31.
[Kotlin] 백준 13199 : 치킨 먹고 싶다 문제 링크 13199번: 치킨 먹고 싶다 서울대학교 301동에는 아는 사람만 아는 “눕치킨”이란 치킨집이 있다. 이 치킨집은 여느 치킨집처럼 치킨을 시킬 때 마다 쿠폰을 C 장 주고, 쿠폰을 F 장 모으면 치킨을 공짜로 시킬 수 있다. 눕 www.acmicpc.net 문제 해설 기본적으로 시킬 수 있는 치킨의 마리수와 치킨을 시키면서 받을 수 있는 쿠폰의 개수는 간단하게 구할 수 있다. val chicken = money / price val coupon = chicken * c 이제 두영이의 경우와 상언이의 경우를 나눠서 생각해보자. 두영이의 경우는 쿠폰으로 시키는 치킨에 쿠폰이 나오지 않는다. 따라서 기본 치킨 마리수에 쿠폰의 개수를 \(f\)로 나눈 값을 그냥 더해주기만 하면 된다. val dooy.. 2024. 3. 25.
[Kotlin] 백준 11082 : 소수를 분수로 문제 링크 11082번: 소수를 분수로 Cube World에서는 모든 유리수를 소수로 표시하고, Baekjoon World에서는 모든 유리수를 분수로 표시합니다. 이때문에 두 나라 간에 오랜 기간 동안 전쟁을 치뤘고, 마침내 서로의 생각을 존중하기로 www.acmicpc.net 문제 해설 소수의 형태로 주어지는 유리수를 기약분수로 치환해야 한다. 우선 입력으로 주어지는 수는 정수, 유한소수, 순환소수 3가지의 경우로 구분할 수 있다. 각 경우에 대해서 생각해보자. 정수인 경우 예제 1과 같이 단순히 분자가 입력으로 주어진 수이고 분모가 1인 형태로 나타내면 된다. println("$decimal/1") 유한소수인 경우 소수부의 길이가 \(n\)이라고 할 때, 유한소수를 분수로 나타내는 가장 쉬운 방법은 .. 2023. 12. 11.
[Kotlin] 백준 1850 : 최대공약수 문제 링크 1850번: 최대공약수 모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오. 예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A www.acmicpc.net 문제 해설 모든 자리가 1로 이루어진 두 수의 최대 공약수를 구해야 한다. 우선 모든 자리가 1로 이루어진 수가 어떻게 구성되는지 보자. \(1111\)의 경우에는 다음과 같이 나눌 수 있다. $$1111=11\times 101$$ 또 다른 수인 \(111111\)은 다음과 같이 나눌 수 있다. $$\begin{align*}111111&=11\times 10101\\&=111\times 1001\end{align*}$$ 자세히 보.. 2023. 11. 11.
[Kotlin] 백준 14277 : 등차 수열과 등비 수열 문제 링크 14277번: 등차 수열과 등비 수열 예제 4의 경우에 4, 20, 100, 452, 476, 500, 524, 548, 572, 596이 정답이다. www.acmicpc.net 문제 해설 문제만 보면 "그냥 등차 수열과 등비 수열을 set에 저장하고 크기를 출력하면 되는게 아닌가?" 싶지만 입력 범위에 함정이 있다. u의 범위가 \(10^{12}\)까지, 즉 1조라는 큰 숫자이기 때문에 a와 b가 1이고 u가 \(10^{12}\)이라면 등차 수열을 구하는데만 10,000초의 시간이 걸리게 될 뿐만 아니라 1조개의 Long타입을 set에 저장하게 되므로 7TB가 넘는 엄청난 양의 메모리를 차지하게 된다. 그렇기 때문에 좀 더 수학적인 방법의 접근이 요구된다. 등차 수열에 포함되는 1 이상, u.. 2022. 12. 21.

티스토리툴바