🔗문제 보러가기 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 🧑🏻‍💻풀이 과정 입력에서 모음과 자음을 각각 분리하여 따로 저장합니다. 아래의 조건을 충족하면서, 저장한 모음과 자음을 조합하여 길이가 L이 될 때까지 암호를 생성합니다. 모음은 최소 1개 ~ 최대 L - 2개까지 암호에 포함될 수 있습니다. 자음은 최소 2개 ~ 최대 L - 1개까지 암호에 포함될 수 있습니다. 생성한 암호의 길이가 L이 되었다면, 암호를 오름차순으로 정렬합니다. 중복을 피하기 위해, 정렬한 암호를 set 자료구조에 저장합니다. 모..

🔗문제 보러가기 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 🧑🏻‍💻풀이 과정 보자마자 조합(Combination)이 떠오르긴 했는데, 이게 정말 단순히 조합만으로 풀릴까?... 시간 초과가 걸리진 않을까?, 중복 계산을 줄일 수 있는 방법이 없을까? 고민을 했는데, 쓸 데 없는 고민이었단 걸 깨달았습니다. 아무래도 집의 개수가 2N개를 넘지 않고, N과 M의 개수가 그렇게 크지 않기 때문인 것 같네요. 게다가, 집과 치킨 집만 사용하니 \( N \times N \) 크기를 모두 탐색할..

🔗문제 보러가기 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 🧑🏻‍💻풀이 과정 Dynamic Programming 문제입니다. \( n = 1\), \( n = 2\), ... 일 때의 경우의 수를 한 번 점검해보면, 패턴이 보이는 것을 알 수 있습니다. /* - 어떤 한 행에 있어서 가질 수 있는 경우의 수는 다음과 같은 3가지 [][], [o][], [][o] */ [][][o][][][o] n = 1 : 1 1 1 n = 2 : 3 2 2 n = 3 : 7 5 5 n = 4 : 17 12 12 ... [ ][ ]의 경우의 수는 n - 1번째의 [ ][ ] + [o][ ] + [ ][o] 값입니다. [o][ ]과 [ ][o]의 경우의 ..

🔗문제 보러가기 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 🧑🏻‍💻풀이 과정 DP(Dynamic Programming)로 풀 수 있습니다. 알고리즘은 다음과 같습니다. 1. (0, 0)부터 시작하여 0행과 0열에 대해 누적합을 저장해 나가며, 초기화를 해줍니다. 예제 입력 1번을 예로 들면 다음과 같이 합니다. // 원본 입력 데이터 1 2 3 4 0 0 0 5 9 8 7 6 // 누적합 적용 후 1 3(2+1) 6(3+3) 10(6+4) 1 (0+1) 0 0 5 10(9+1) 8 7 6 2..

🔗문제 보러가기 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 🧑🏻‍💻풀이 과정 피보나치 함수를 호출했을 때, \( n = 0 \) 또는 \( n = 1 \)일 때의 0과 1의 출력 개수를 세야 합니다. (즉, 위 문제에서 주어진 소스 코드에서 if(n == 0)과 if (n==1)에 해당할 경우) 1. Top-down 방식으로 DP 배열을 통해 중복 계산 최소화 방법 시도 (실패) 피보나치 함수를 재귀로 구현했을 때의 문제점이 바로 중복 계산입니다. 중복 계산이 이루어지기에 시간이 터무니없이 많이 걸리는 것이고, 이것을 개선하기 위해 DP 배열을 사용하여 이미 계산된 N이라면 계산하지 않는 것이죠. 하..

🔗문제 보러가기 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 🧑🏻‍💻풀이 과정 \( n = 1\)부터 하나씩 그려보면, 피보나치 수열의 규칙이 생깁니다. \( n = 1\)과 \( n = 2\)를 베이스로 삼아, \( n = 3\)부터는 \( n - 2\)와 \( n - 1\)을 가지고 조합해 나가는 방식이다 보니, 피보나치 수열과 같은 규칙이 생기는 것 같네요. ✏️ 소스 코드 및 결과 #include #include using namespace std; void SetFastIO() { ios::sync_with_stdio(..