문제 링크 https://www.acmicpc.net/problem/20166 20166번: 문자열 지옥에 빠진 호석 K개의 줄에 걸쳐서, 신이 좋아하는 문자열을 만들 수 있는 경우의 수를 순서대로 출력한다. www.acmicpc.net 문제 풀이 중복 방문을 허용하고, 상하좌우 대각선(8개 방향) 방향으로 이동하여 문자열을 만듦 참고. 시간 복잡도 행 * 열 * (8방향으로 이동^최대 단어 길이 5) = 100 * (8^5) = 3,276,800 (1초안에 수행 가능) 참고. 방향 이동 관련하여 ( 3 x 3 ) (0, 0) 좌표에서 아래 대각선 방향으로 이동할 경우 맵의 범위를 벗나게 될 것이다 (-1, -1) (-1, 0) (-1, 1) (0, -1) 시작 (0, 1) (1, -1) (1, 0) (..

문제 링크 https://www.acmicpc.net/problem/20164 20164번: 홀수 홀릭 호석 호석이는 짝수랑 홀수 중에서 이니셜이 같은 홀수를 더 좋아한다. 운전을 하던 호석이는 앞차의 번호판이 홀수로 가득할 때 사랑스러움을 느낄 정도이다. 전화번호도 홀수만 있고 싶다. 그렇게 www.acmicpc.net 문제 풀이 하나의 수가 주어졌을 때 호석이는 한 번의 연산에서 다음과 같은 순서를 거친다. 1. 수의 각 자리 숫자 중에서 홀수의 개수를 종이에 적는다. 2. 수가 한 자리이면 더 이상 아무것도 하지 못하고 종료한다. 3. 수가 두 자리이면 2개로 나눠서 합을 구하여 새로운 수로 생각한다. 4. 수가 세 자리 이상이면 임의의 위치에서 끊어서 3개의 수로 분할하고, 3개를 더한 값을 새로..

문제 링크 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱 www.acmicpc.net 풀이 - DFS로 연산자에 대한 순열(Permutation)을 구한 후 연산 결과값 구함 - N(2 ≤ N ≤ 11) 이므로 최대 연산자 개수는 10개, 순열 10! = 3,628,800 - 시간복잡도 O(N! * N ) = O(10! * 11) = 약 3,600만번 이므로 풀이가능 제출 코드 풀이1. 연산자 순열을 구한 후 연..