본문 바로가기
728x90

PS/백준15

[백준/BOJ] 전생했더니 슬라임 연구자였던 건에 대하여 (Hard) 문제링크 https://www.acmicpc.net/problem/14698 14698번: 전생했더니 슬라임 연구자였던 건에 대하여 (Hard) 각 테스트 케이스마다 슬라임을 끝까지 합성했을 때 청구될 비용의 최솟값을 1, 000, 000, 007로 나눈 나머지를 출력한다. 전기 에너지가 전혀 필요하지 않은 경우엔 1 을 출력한다. www.acmicpc.net 1. 핵심 슬라임 합성 비용을 최소로 하기 위해서는 "작은" 슬라임들(이미 존재하는 슬라임과 새롭게 합성된 슬라임)부터 합성해야한다. 작은 슬라임을 뽑기 위해서 우선순위 큐(min heap)를 사용한다. MOD 에 대해서(시간초과 발생의 원인1) > MOD 문제 항상 주의!! 파이썬에서는 계속 곱하면 숫자가 끊임없이 커지게 되면서 시간복잡도가 매우.. 2024. 4. 23.
[누적합] 출석체크 문제링크 https://www.acmicpc.net/problem/20438 20438번: 출석체크 1번째 줄에 학생의 수 N, 졸고 있는 학생의 수 K, 지환이가 출석 코드를 보낼 학생의 수 Q, 주어질 구간의 수 M이 주어진다. (1 ≤ K, Q ≤ N ≤ 5,000, 1 ≤ M ≤ 50,000) 2번째 줄과 3번째 줄에 각각 K명 www.acmicpc.net 1. 핵심 학생의 분류 출석 코드 받고 졸지 않은 학생 → 자신의 배수 번호에 전파 가능 출석 코드를 받고 졸은 학생 → 전파 불가 / 코드 받을 수 없음 출석 코드를 받지 않고 졸지 않은 학생 학생 → 전파 불가 / 코드는 받을 수 있음 출석 코드를 받지 않고 졸은은 학생 → 전파 불가 / 코드 받을 수 없음 코드 해설 코드를 받은 학생들 중.. 2024. 4. 1.
[그리디] 전구와 스위치(Python) 문제링크 https://www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 www.acmicpc.net 1. 핵심 좌우 상태 반전 그리디 유형 같은 곳을 2번 선택하면 선택하지 않는 것과 동일하므로 같은 곳을 2번 선택하지는 않는다. 순차적으로 진행하면서 눌러야하는 위치 판단하는게 유리 첫번째 위치가 선택되는지 안되는지 경우를 나누어서 생각 순차적으로 파악한 후에 마지막 원소가 동일한지 동일하지 않은지 판단한다. 마지막 원소가 같다면 잘 변경된 것이고 마지막 원.. 2024. 2. 18.
[DP] 호텔(Python) 문제링크 https://www.acmicpc.net/problem/1106 1106번: 호텔 첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 www.acmicpc.net 1. 핵심 유형2-1. item을 중복해서 사용 가능 + 유형3. weight를 특정할 수 없는 경우 최소 비용을 고르기 때문에 보통은 도시(item) / 고객수(weight) / 비용(value)로 고객수 i명을 확보하기 위한 비용j라고 dp[i][j]를 정의할 수 있다. 하지만 문제는, 고객의 수, 즉 weight가 '무한'이므로 고객수를 특정할 수 없다는 것이다. 따라서 유형3으.. 2024. 2. 16.
[백준/BOJ] 4233번 - 가짜 소수 (Python) 문제링크 https://www.acmicpc.net/problem/4233 4233번: 가짜소수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, p와 a를 포함하고 있다. 입력의 마지막 줄에는 "0 0"이 주어진다. (2 < p ≤ 1,000,000,000, 1 < a < p) www.acmicpc.net 1. 핵심 1) 10억 이상 소수 판정 - 에라토스테네스의 체로는 10억 이상의 소수 판정 불가능 - 소수 판정 하는 방법: 제곱근까지 나눠서 확인하기 2) 비트연산을 활용한 거듭제곱 2. 코드(Python) # https://www.acmicpc.net/problem/4233 # 소수 구하기 def isPrime(n): for i in range(2, i.. 2023. 11. 2.
[백준/BOJ] 27172번 - 수 나누기 게임 (Python) 문제링크 https://www.acmicpc.net/problem/1509 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net 1. 핵심 1) 유형 DP: [@+작은 팰린드롬+@] 작은 팰린드롬 양쪽의 @만 확인해서 더 큰 팰린드롬 [@+작은 팰린드롬+@] 인지 확인 2) 왜 reversed(range(n))을 할까? IF. reveresed가 아니라 range(n)을 생각해보자. → 인덱스의 범위가 (0, x)가 팰린드롬을 확인하기 위해서는 작.. 2023. 10. 28.
728x90
반응형

티스토리툴바