[백준] 10942번: 펠린드롬? - 파이썬
2023. 1. 16. 18:57ㆍ백준 & 프로그래머스
문제보기
https://www.acmicpc.net/problem/10942
10942번: 팰린드롬?
총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다.
www.acmicpc.net
풀이 및 코드
해당 문제는 dp문제로 s부터 e까지의 펠린드롬을 판단하기 위해서는 두 가지를 먼저 판단해야한다.
- s + 1, e - 1이 펠린드롬인가.
- s번째와 e번째 숫자가 서로 같은가.
물론 s부터 e까지 숫자들을 비교해 가면서 판단할 수도 있지만, 이를 이용하면 dp를 이용할 수 없다. 즉 메모제이션을 사용해 s, e까지를 저장하고 나중에 이 범위가 쓰인다면 빠르게 판단할 수 있게 된다.
'백준 & 프로그래머스' 카테고리의 다른 글
| [백준] 12865번: 평범한 배낭 (Knapsack Problem) - python (0) | 2023.01.27 |
|---|---|
| [백준] 14442번: 벽 부수고 이동하기 2 - 파이썬 (0) | 2023.01.27 |
| [백준] 2186번: 문자판 - 파이썬 (0) | 2023.01.12 |
| [백준] 1766번: 문제집 - 파이썬 (0) | 2023.01.11 |
| [백준] 1461번: 도서관 - python (0) | 2023.01.10 |