1141번: 접두사 접두사X 집합이란 집합의 어떤 한 단어가, 다른 단어의 접두어가 되지 않는 집합이다. 예를 들어, {hello}, {hello, goodbye, giant, hi}, 비어있는 집합은 모두 접두사X 집합이다. 하지만, {hello, hell}, {giant, www.acmicpc.net 문자열들을 정렬해서 해결할 수 있는 문제이다. 단어 A가 단어 B의 접두사가 되려면 반드시 B의 길이가 A의 길이 이상임을 이용한다. 1. 입력받은 단어를 길이가 짧은 순으로 정렬한 다음, 2. 모든 단어를 확인한다. 한 단어를 확인할 때엔 그보다 길이가 같거나 긴 모든 단어를 확인한다. 3. 자신보다 길이가 같거나 긴 단어에 대해 확인 중인 단어가 접두사가 아니라면, 그 단어는 접두사X 집합에 들어갈 ..

2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 주어진 보드에서 아직 채워지지 않은 칸을 채워서, 사전 순으로 가장 앞선 해답을 출력하는 문제이다. 문제 해결을 위한 대략적인 아이디어는 다음과 같다. 9개의 행, 열, 3*3 박스에는 1부터 9까지 단 한 번씩 모두 들어가야 하니 이를 위한 flag 배열을 선언하였다. 보드 상태를 입력받을 때, 빈 칸의 개수를 num_of_zero 변수에 저장하고 그 칸의 좌표를 queue 안에 넣어주었다. 9appendleft를 이용하기 위해 deque를 사용했다) 그..

13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 처음에 문제를 잘못 봐 구슬이 각각 하나씩 있는 줄 모르고 '이거 무조건 메모리 초과 뜰 거 같은데...' 하면서 2시간을 낭비하고 만 문제이다. (사실 문제를 제대로 본 다음에도 제대로 못 풀었다) 문제 해결을 위한 대략적인 아이디어는 다음과 같다. 보드의 상태를 직접 변경하는 것이 아닌, 보드를 확인하며 구슬의 좌표만을 변경하는 것이 핵심이다. 이를 위해 처음 구슬들의 좌표를 확인해서 저장한다. 구슬을 움직일 ..

10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 먼저 유의해야 할 점은, 팰린드롬 여부를 판정 시 N개의 숫자들을 하나의 char처럼 취급해야 한다는 점이다. 예를 들어 123, 3, 123은 팰린드롬이 되고 123, 3, 321은 팰린드롬이 아니게 된다. 다음으로, a번째 수부터 b번째 수가 팰린드롬을 이룬다는 것은 a번째 수와 b번째 수가 같다 a+1번째 수와 b-1번째 수가 팰린드롬을 이룬다 이 두 가지 조건과 동치임을 어렵지 않게 생각할 수 있다. 따라서, DP를 이용해 문제를 해결할 수 있다. 하나의 수의 경우 반드시 팰린드롬을 이루니 초기..