본문 바로가기
728x90

27172번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.
[백준/BOJ] 27172번 - 수 나누기 게임 (Python) · 문제링크 https://www.acmicpc.net/problem/27172 27172번: 수 나누기 게임 《보드게임컵》을 준비하다 지친 은하는 보드게임컵 참가자들을 경기장에 몰아넣고 결투를 시키는 게임 《수 나누기 게임》을 만들었습니다. 《수 나누기 게임》의 규칙은 다음과 같습니다. www.acmicpc.net · 핵심 : 약수 + 시간복잡도 → 문제 요약 : 내가 다른 수를 나눠서 나머지가 0이면 +1 득점, 나뉘어진 수를 가진 상대방은 -1 감점 1. 시간복잡도 계산 → 바로 떠오르는 풀이는 이중 for문 써서 전부 확인하는 방법 → N = 100,000이므로 이중for문 사용하면 반드시 시간초과 발생 2. 약수 구하기 → 제곱근까지만 확인하기 : 시간복잡도 O(N^(1/2)) 3. +1 과 -.. 2023. 10. 17.
728x90
반응형

티스토리툴바