[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

[BOJ] 백준 2503 숫자 야구 / 완전 탐색(Brute-force Search)

💣 문제 이해 영수는 1에서 9까지의 서로 다른 숫자 세 개로 구성된 세 자리 수를 마음속으로 생각한다. (예: 324) 민혁이는 1에서 9까지의 서로 다른 숫자 세 개로 구성된 세 자리 수를 영수에게 묻는다. (예: 123) 민혁이가 말한 세 자리 수에 있는 숫자들 중 하나가 영수의 세 자리 수의 동일한 자리에 위치하면 스트라이크 한 번으로 센다. 숫자가 영수의 세 자리 수에 있긴 하나 다른 자리에 위치하면 볼 한 번으로 센다. 민혁이의 물음들과 각각의 물음에 대한 영수의 답이 입력으로 주어질 때 영수가 생각하고 있을 가능성이 있는 답의 총 개수를 출력하는 프로그램을 작성하시오. 문제에 제시된 다음과 같은 조건들을 정리하면 다음과 같다. 1. 영수와 민혁이가 생각한 수는 세 자리 수이고, 각 자리 수는..

→2020.02.24

[BOJ] 백준 3085 사탕 게임 / 완전 탐색(Brute-force Search)

* 예외 처리를 잘하자 💣 문제 이해 1. 행으로 인접한 두 칸을 고르고 교환한다(swap) 2. 행과 열에서 가장 길게 연속해있는 사탕개수를 찾는다. 3. 열로 인접한 두 칸을 고르고 교환한다(swap) 4. 행과 열에서 가장 길게 연속해있는 사탕개수를 찾는다. 보통 컴퓨터가 1초에 약 1억번의 연산을 한다. 이 문제에서 배열의 최대 크기라고 해봐야 50*50 이므로 단순하게 모든 경우를 하나하나 따져보아도 50*50*(50*50+50*50) = 12,500,000 이므로 완전 탐색(Brute-force Search) 방식을 사용하기로 했다. 💭 풀이 과정 작성 언어: C++ #include #include using namespace std; int num = 0; char arr[60][60] = ..

→2020.02.19

[BOJ] 백준 1011 Fly me to the Alpha Centauri

* 변수 오버플로우를 잘 고려하자!!! 💣 문제 이해 약간의 수학적인 규칙을 찾는 것이 필요한 문제였다. 첫 번째는 무조건 1 만큼 이동, 이후로는 다음과 같은 규칙이 있다. 이전에 1 만큼 움직였다면 이번에는 0, 1, 2 중 선택해서 이동이 가능하다. 이전에 2 만큼 움직였다면 이번에는 1, 2, 3 중 선택해서 이동이 가능하다. 거리를 입력받았을 때, 이 규칙 내에서 처음 지점에서 끝 지점까지 정확하게 도착할 수 있는 최소 이동 횟수를 구하여 출력하면 된다. 💭 풀이 과정 이동거리를 1부터 차례대로 적어가며 규칙을 찾아보았다. 이동 거리 이동 방식 이동 횟수 1 1 1 2 1 1 2 3 1 1 1 3 4 1 2 1 3 5 1 2 1 1 4 6 1 2 2 1 4 7 1 2 2 1 1 5 8 1 2 2..

→2020.01.07

[BOJ] 백준 2869 달팽이는 올라가고 싶다

* 문제 난이도가 어려운 것은 아니지만, 시간복잡도 계산의 중요성을 새삼 느끼게 한 문제라 기록한다. 💣 문제 이해 문제에 나와있는 것처럼 달팽이는 낮에는 up만큼 올라가고 밤에는 down만큼 미끄러진다. 그러나, 정상에 올라간 후에는 미끄러지지 않는다. 즉, 낮에 up만큼 올라간 후에 나무높이 tree를 넘는다면 down만큼 차감하지 않아도 된다는 것이다. 그런데 간과하면 안 되는 것이 있다. 입력이 최대 10억까지 가능하다는 것, 그리고 시간제한이 0.15초라는 것... 💭 풀이 과정 처음에 작성한 소스이다. (시간 초과) 작성 언어: C++ #include int main(){ int up, down, plus = 0, tree, day = 0; scanf("%d %d %d", &up, &down,..

→2020.01.03

[BOJ] 백준 2447 별 찍기 - 10

재귀함수를 정의해 봅시다. 문제 예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요. 입력 첫째 줄에 N이 주어진다. N은 항상 3의 제곱꼴인 수이다. (3, 9, 27, ...) (N=3k, 1 ≤ k < 8) 출력 첫째 줄부터 N번째 줄까지 별을 출력한다. Input 27 Output My Solution #include using namespace std; char arr[7000][7000] = {0,}; void inpStar(int n, int x, int y){ if(n == 1){ arr[x][y] = '*'; return; } int val = n/3; for(int i = 0; i < 3; ++i){ for(int j = 0; j < 3; ++j){ if(i == 1 && j == 1) ..

→2019.10.11