[BOJ] 백준 10844 쉬운 계단 수 / 동적 계획법(Dynamic-Programming)

💣 문제 이해 1. 45656 과 같이 모든 자리 수가 인접한 자리 수와 1 차이날 때, 그 수를 계단 수 라고 한다. 2. 입력으로 1~100 사이의 자연수 N 이 주어진다. 3. N 자리 자연수 중 계단 수가 총 몇 개인지 찾아 출력하면 된다. 동적 계획법(Dynamic Programming) 방식을 사용했다. 💭 풀이 과정 N = 1 인 경우, 1, 2, 3, 4, 5, 6, 7, 8, 9 가 가능하다. 문제에 제시된 조건에 따라 0은 불가하다. N = 2 인 경우, 10, 12, 21, 23, 32, 34, .... 98 가 가능하다. 1 ~ 9 사이 수를 십의 자리로 하여 일의 자리는 -1 한 수 또는 +1 한 수라는 것을 알 수 있다. 점화식으로 정리하자면 다음과 같다. dp[i][j] = d..

→2020.03.06

[BOJ] 백준 1699 제곱수의 합 / 동적 계획법(Dynamic-Programming)

💣 문제 이해 1. 어떤 자연수 N 은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 2. 주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구해야 한다. 동적 계획법(Dynamic Programming) 방식을 사용했다. 💭 풀이 과정 DP 방식을 활용하기로 하면서 제곱수가 1 로만 구성되어있을 때, 1, 2 로 구성되어 있을 때, 1, 2, 3 으로 구성되어 있을 때 .... 등등 순차적으로 하나 씩 포함하며 모든 경우를 따져보기로 했다. N 이 15 인 경우를 예로 들어보자면 다음과 같다. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 각 인덱스가 입력으로 받는 자연수 N 이다. N = 5 의..

→2020.03.04

[BOJ] 백준 11726 2xn 타일링 / 동적 계획법(Dynamic-Programming)

💣 문제 이해 앞에 풀었던 2193번 이친수, 1904번 01타일 과 상당히 비슷한 문제이다. 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 출력하면 된다. 동적 계획법(Dynamic Programming) 방식을 사용했다. 💭 풀이 과정 | 를 2x1 사각형, == 를 1x2 사각형으로 가정하겠다. N = 1 인 경우 1가지 | N = 2 인 경우 2가지 | | , == N = 3 인 경우 3가지 | | | , == | , | == N = 4 인 경우 5가지 | | | | , == | | , | | == , | == | , == == 이런 방식으로 변화한다. 여기서 두 가지의 규칙을 찾을 수 있었다. 1) N-2 번째 경우의 수와 N-1 번째 경우의 수를 합한 것이 N 번째 경우의..

→2020.03.04

[BOJ] 백준 1904 01타일 / 동적 계획법(Dynamic-Programming)

💣 문제 이해 앞에 풀었던 2193번 이친수 와 상당히 비슷한 문제이다. 1. 0 과 1 로 이진수를 만들고자 한다. 2. 0 은 무조건 00 형태로만 쓰이고 1 은 원하는 대로 쓸 수 있다. 3. 입력으로 주어진 N 자리 수의 이진수를 총 몇 가지 만들 수 있는지 구하면 된다. 4. !! 찾은 수열의 개수를 15746 으로 나눈 나머지를 출력해야 한다 !! 동적 계획법(Dynamic Programming) 방식을 사용했다. 💭 풀이 과정 N = 1 인 경우 1 로 총 1가지 N = 2 인 경우 11, 00 으로 총 2가지 N = 3 인 경우 111, 100, 001 으로 총 3가지 N = 4 인 경우 1111, 1001, 1100, 0011, 0000 으로 총 5가지 N = 5 인 경우 11111, 1..

→2020.03.04

[BOJ] 백준 2193 이친수 / 동적 계획법(Dynamic-Programming)

💣 문제 이해 1. 첫 번째 자리가 1로 시작하는 수이다. 2. 1과 1이 인접할 수 없다고 했으니, 두 번째 자리는 0 이다. 3. N 자릿수 중에서 이러한 규칙을 만족하는 수의 개수를 구해야 한다. 동적 계획법(Dynamic Programming) 방식을 사용했다. 💭 풀이 과정 N = 1 인 경우는 1 하나밖에 없다. => 1 N = 2 인 경우는 10 하나밖에 없다. => 1 N = 3 인 경우는 100, 101 두 가지이다. => 2 N = 4 인 경우는 1000, 1001, 1010 세 가지이다. => 3 N = 5 인 경우는 10000, 10001, 10010, 10100, 10101 다섯 가지이다. => 5 이 규칙을 토대로 발견할 수 있는 것은 1) 바로 앞 케이스에 따라 다음 케이스가 ..

→2020.03.04

[BOJ] 백준 2294 동전 2 / 동적 계획법(Dynamic-Programming)

💣 문제 이해 1. n가지 종류의 동전이 주어진다. 2. 이 동전들을 사용해서, 그 가치의 합이 k원이 되야한다. 3. 위 조건을 만족하는 최소의 동전의 개수를 구하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다. 4. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 동적 계획법(Dynamic Programming) 방식을 사용했다. 💭 풀이 과정 1 5 12 coinArr은 동전 가치를 저장하는 배열 이다. 주어진 동전 종류는 1, 5, 12 세 가지 이다. 이때 std::sort 함수를 사용해서 동전 종류를 오름차순 정렬 해둔다. 0 초기값 초기값 초기값 초기값 초기값 초기값 초기값 초기값 초기값 초기값 초기값 초기값 초기값 초기값 초기값 dp 는 인덱스가 값이고 그 값을 채울 ..

→2020.03.03

[BOJ] 백준 9465 스티커 / 동적 계획법(Dynamic-Programming)

💣 문제 이해 각 스티커에는 점수가 부여되어 있으며, 한 스티커를 선택하면 그 상하좌우의 스티커는 선택할 수 없다는 조건이 주어져있다. 2행 n열의 스티커 중에서 조건을 만족하며 선택했을 때, 얻을 수 있는 최대의 점수를 구하는 문제이다. 한 스티커를 선택함에 따라 다음 선택지가 결정될 것만 같아 그리디(Greedy algorithm) 방식일 것 같으나, 그렇게 해서는 진짜 최대값을 찾을 수가 없다. 모든 가능한 선택지에 대해 각각 구할 수 있는 최대값을 찾아야한다고 판단했다. 동적 계획법(Dynamic Programming) 방식을 사용했다. 💭 풀이 과정 첫 번째 테스트 케이스의 경우이다. 50 10 100 20 40 30 50 70 10 60 출발점은 50 또는 30이다. 50을 선택하는 경우, 우..

→2020.03.02

[BOJ] 백준 1463 1로 만들기 / 동적 계획법(Dynamic-Programming)

💣 문제 이해 1. X가 3으로 나누어 떨어지면, 3으로 나눈다. 2. X가 2로 나누어 떨어지면, 2로 나눈다. 3. 1을 뺀다. 4, 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 이용하여 1을 만들고자 한다. 이때, 필요한 연산 횟수의 최소값을 구하는 것이 목표이다. 동적 계획법(Dynamic Programming) 방식을 사용했다. 💭 풀이 과정 바텀업(Bottom-Up) 방식으로 구현했다. (다른 분들 풀이를 보니, 탑다운 방식도 있고 다양했다.. 나빼고 다천재인듯...) 입력 값의 최대가 106 (1,000,000) 이므로 크기가 100만이고 각 원소를 100만으로 초기화한 int 형 벡터를 사용했다. 벡터 내부 각 원소는 그 인덱스 번호에 해당하는 숫자의 연산 횟수를 값으로 가지고 있다...

→2020.02.27

[BOJ] 백준 1182 부분수열의 합 / 완전 탐색(Brute-force Search)

💣 문제 이해 N개 (20개 이하) 의 정수로 이루어진 수열이 입력으로 주어지고 그 수열 내에서 원소 개수가 양수인 부분수열 중 합이 S 인 수열의 개수를 구하라는 문제이다. 문제를 풀면서 DFS, 백트래킹이 생각났고, 실제 다른 블로거 분들도 그렇게 풀이를 하는 경우도 있었다. DFS와 백트래킹 문제풀이를 할 때, 그 방식으로도 풀어보기로 하고, 이번에도 또한 완전 탐색(Brute-force Search) 방식을 사용하기로 했다. (이름은 그렇고 암튼 재귀호출함..) 💭 풀이 과정 작성 언어: C++ #include int num[25] = {0,}; int inpCnt = 0, inpSum = 0, answer = 0; void count(int pIndex, int pSum){ pSum += num..

→2020.02.26

[BOJ] 백준 1018 체스판 다시 칠하기 / 완전 탐색(Brute-force Search)

💣 문제 이해 1. 입력받을 체스판은 8*8 이상의 크기를 가진다. 2. 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우 두 종류의 판으로 만들고자 한다. 3. 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 4. 8*8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠하려고 한다. 이때, 8*8 크기는 체스판 내 어디서든 고를 수 있다. 5. 다시 칠해야 하는 칸의 최소 개수를 찾아야 한다. 완전 탐색(Brute-force Search) 방식을 사용했다. 💭 풀이 과정 먼저 흰색 칸으로 시작하는 8*8 체스판과 검정색 칸으로 시작하는 8*8 체스판을 string 배열로 만들어두었다. 소스코드 진행 방식은 다음과 같다. 입..

→2020.02.25