문제 28709번: 와일드카드 괄호 문자열첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B'www.acmicpc.net  분석 괄호의 쌍이 맞도록 문자열을 처리하는 문제입니다.얼핏 보면 9012 - 괄호 와 같은 스택 문제처럼 보이기도 합니다만, '*' 문자를 '(', ')'로 이루어진 길이 0 이상의 문자열로 대체할 수 있다는 강력한 조건이 붙어 있습니다.원하는 길이의 문자열을 붙일 수도 있고, 심지어 붙이지 않을 수도 있기 때문에 '*' 문자열이 단 하나라도 존재한다면 항상 올바른 괄호 문자열로 만들 수도 있겠다는 생..

문제 13460번: 구슬 탈출 2첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B'www.acmicpc.net 분석 시뮬레이션 문제입니다.구슬이 한 개라면 그렇게 어렵지 않을 것 같지만, 구슬이 두 개이기 때문에 껄끄러운 부분이 몇 가지 생깁니다.먼저 두 구슬이 동시에 구멍을 탈출하는 경우입니다. 이 경우 그냥 실패로 처리하면 됩니다.두 번째는 두 구슬이 붙어 있는 경우입니다. 구슬이 움직일 자리에 다른 구슬이 이미 이동을 완료하여 멈춰 있는 상태라면, 더 이상 이동하지 못합니다. 만약 구슬이 나란히 붙어있는 상태에서 보..

문제  15685번: 드래곤 커브첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커www.acmicpc.net 이름이 멋져서 오랫동안 풀고 싶었는데, 이제야 풀게 되었습니다. 분석 100x100 크기의 격자 위에 정해진 규칙에 따라 좌표평면을 잇는 선분을 긋고, 모든 선분을 그었을 때 1x1 크기인 정사각형의 네 꼭짓점이 모두 선분 위의 점이 되는 정사각형의 개수를 구하는 문제입니다. N세대 드래곤 커브의 생성 규칙에 대해 생각해 보겠습니다.N세대 드래곤 커브를 만들기 위해서는 시작 점, 시작 방향, (목표)세대가 필요합니다.예제에 주어진 대..

문제 1182번: 부분수열의 합첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.www.acmicpc.net 분석 정수로 이루어진 최대 길이 20의 수열이 주어지고, 그 수열의 합이 S가 되는 경우의 수를 구하는 문제입니다.전체 수열을 순회하며 이번 원소를 고를지, 고르지 않을 지 선택해나간다고 가정한다면, 수열의 길이가 1 늘어날 때마다 경우의 수는 2배로 늘어납니다. 즉 수열의 길이 N에 따른 시간 복잡도는 O(2^N)이 되겠습니다.시간 복잡도가 매우 크기 때문에 N이 조금만 커지더라도 사용할 수 없는 방법입니다. 그러나 이번 ..