Algorithm/BOJ114 [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] 백준 6523 : 요세푸스 한 번 더! 문제 링크 : https://www.acmicpc.net/problem/6523문제 해설일종의 구현 문제. 따로 특별한 알고리즘이 필요하진 않다. 문제에서 각 사람들은 두번째에 걸렸을 때 술을 마시게 되고, 누구든 세 번 걸린다면 모두 집에 간다는 내용이 있다. 술을 마시지 않고 집으로 가는 사람의 수를 출력해야 하기 때문에 누군가 두번째 걸렸을 때 술을 마신 사람의 수를 더하고, 세번째 걸린다면 해당 테스트 케이스를 종료하면 된다. 각 사람들이 걸린 횟수를 기록하기 위해 HashMap을 사용한다. 정수배열을 사용해서 기록할 수도 있겠으나, 크기가 최대 10억인 정수배열을 선언하게 되어 어마어마한 메모리를 차지하게 되는 문제가 있어서 사용할 수 없다. 현재 사람의 번호가 \(x\)일 때 다음 사람의 번호.. 2024. 6. 10. [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] 백준 17612 : 쇼핑몰 문제 링크 : https://www.acmicpc.net/problem/17612문제 해설일종의 정렬 문제. 계산대를 우선순위 큐로, 빠져나온 고객을 리스트로 생각해볼 수 있다. 고객을 정렬해야 하니 고객 정보를 어떻게 할지 생각해보자. 각각의 고객은 회원번호와 계산해야 할 물건의 개수를 갖고 있다. 그리고 계산해야 할 물건의 개수는 계산에 걸리는 시간과 같다. 우선 계산대에 들어가는 순서부터 생각해보면 가장 시간이 적게 걸리는 계산대에 먼저 들어가고, 같은 시간이 걸리는 계산대는 번호가 빠른곳부터 들어가게 된다. 모든 고객은 계산대에 들어가게 되니 각 고객 번호와 계산에 걸리는 시간에 더불어 들어간 계산대 번호를 속성으로 넣어주고, 시간과 계산대 번호를 정렬 기준으로 정해준다.private class .. 2024. 5. 22. [Kotlin] 백준 28078 : 중력 큐 문제 링크 : https://www.acmicpc.net/problem/28078문제 해설조금 변형된 큐 문제. 큐의 방향에 따라 내용을 처리해야 한다. 큐의 방향에 따라서 공이 앞부분으로 나올 수도 있고 뒤부분으로 나올 수도 있기 때문에 덱(Deque)을 사용한다. 편의 상 본문에서는 큐라고 언급한다. 큐의 방향에 대해 생각해보자. 큐의 방향은 90도씩 회전하는 4가지 방향만 존재하기 때문에 큐의 앞부분이 바라보는 방향을 오른쪽부터 시계방향으로 0, 1, 2, 3으로 지정할 수 있다.var direction = 0 // 0: right, 1: down, 2: left, 3: up각 쿼리에 대한 동작을 구현하기 전에 큐에서 공의 개수와 가림막의 개수를 구하는 방법을 생각해보자. 단순히 count() 메소.. 2024. 5. 17. [Kotlin] 백준 1322 : X와 K 문제 링크 : https://www.acmicpc.net/problem/1322문제 해설\(X+Y=X|Y\)가 되는 \(Y\) 중 \(K\)번째 수를 구해야 한다. \(X+Y=X|Y\)가 성립하는 것이 어떤 의미인지 생각해보기 위해 2진수의 경우를 생각해보자. \(X|Y\)는 2개의 2진수 중 하나라도 1인 모든 비트를 1로 만들어주는 연산이다. \(X+Y\)는 아래 그림의 \(101001+1110\)의 경우를 보자.2개의 2진수 중 하나만 1인 비트만 1이 되고, 둘 다 1인 비트는 받아올림 비트가 발생하면서 0이 된다. 여기까지 보면 \(Y\)가 \(X\)에서 0인 비트만 1로 채워나가서 받아올림 비트가 발생하지 않는 수일 때 \(X+Y=X|Y\)가 성립한다는 것을 알 수 있다. 그러면 이제 \(K\.. 2024. 5. 13. 이전 1 2 3 4 ··· 15 다음
