🔗문제 보러가기 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 🧑🏻‍💻풀이 과정 N자리 숫자에서 일의 자리가 0 ~ 9로 끝나는 계단 수들의 개수를 알아봅시다. 먼저, \( N = 1\)일 때는 다음과 같습니다. [ N = 1 일 때 ] i = 0 i = 1 i = 2 i = 3 i = 4 i = 5 i = 6 i = 7 i = 8 i = 9 0 1 1 1 1 1 1 1 1 1 [ N = 2 일 때 ] i = 0 i = 1 i = 2 i = 3 i = 4 i = 5 i = 6 i = 7 i = 8 i = 9 1 1 2 2 2 2 2 2 2 1 [ N = 3 일 때 ] i = 0 i = 1 i = 2 i = 3 i = 4 i..

🔗문제 보러가기 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 🧑🏻‍💻풀이 과정 문제 로직 자체는 어렵지 않은데, 구현할 게 많아서 상당히 귀찮았던 문제입니다. 문제를 보면, 다음과 같은 문장을 읽을 수 있습니다. 뱀의 머리가 먼저 한 칸 이동합니다. 그 위치에 사과가 없다면, 꼬리도 한 칸 이동하고, 사과가 있다면 꼬리는 이동하지 않습니다. 위 문장을 구현하려면, 뱀의 꼬리가 이동할 방향에 대한 정보가 필요합니다. 뱀의 꼬리가 이동해야 할 방향은 이전까지 뱀의 머리가 이동했던 방향들이므로, 뱀의 머리가 이동했던 ..

🔗문제 보러가기 16198번: 에너지 모으기 N개의 에너지 구슬이 일렬로 놓여져 있고, 에너지 구슬을 이용해서 에너지를 모으려고 한다. i번째 에너지 구슬의 무게는 Wi이고, 에너지를 모으는 방법은 다음과 같으며, 반복해서 사용할 수 있 www.acmicpc.net 🧑🏻‍💻풀이 과정 에너지 값들을 vector weights에 저장한 후, weights의 크기가 2가 될 때까지 다음 과정을 반복합니다. 정답을 저장할 변수(maxEnegy)와 현재 경우의 수의 합계를 저장할 변수(sum)를 생성합니다. weights를 i = 1부터 i = weights.size() - 1까지 for 문으로 순회합니다. weights[i - 1] x weights[i + 1]의 값을 sum에 더합니다. weights[i] 원..

🔗문제 보러가기 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]의 경우의 ..