10942번
-
백준 10942번 팰린드롬? :: 마이구미알고리즘 풀이/동적계획법 2017. 6. 30. 19:55
이번 글은 백준 알고리즘 문제 10942번 팰린드롬? 을 다뤄본다.로켓처럼 빠른 회사인 쿠* 개발자 코딩 테스트에서 출제된 문제이기도 하다.문제 풀이의 최적의 접근법은 동적계획법이다.여기서는 동적계획법과 순수한 다른 방법을 다룬다. 팰린드롬(palindrome)이란 앞에서부터 읽으나 뒤에서부터 읽으나 같은 단어를 말한다. 'aba'나 'a'와 같은 단어는 팰린드롬이며, 'abaccbcb'나 'anavolimilana'와 같은 단어는 팰린드롬이 아니다 명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다.먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그 다음, 명우에게 질문을 총 M번 한다.각 질문은 두 정수 S와 E로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우..