답은 알고리즘 뿐이야!

문제 출저 : https://www.acmicpc.net/problem/2294 풀이 : DP 문제입니다. 동전과 가치가 주어졌을때 가치의 합이 k가 되도록 하는 문제입니다. 데이터를 쌓을 때 주어진 value로 부터 시작해 한 칸 씩 진행하며 (계산중인 가치) 와 (계산중인 가치 - 현재가치 + 1) 중 최소값을 저장합니다. 만약 +=value로 껑충 껑충 뛰게 된다면 3 24 1 7 10 같은 경우 3이 나와야 하는데 놓칠 수도 있습니다. 필자가 그랬음 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 #include int n,k,cache[10001],value; int FindMin(int a, int b) { if (a

문제 출저 : https://www.acmicpc.net/problem/10844 풀이 : DP문제입니다. 0으로 시작 하는 수는 없지만 0으로 끝나는 수는있음에 주의합시다. 이 문제도 [11057] 오르막 수 이 문제와 마찬가지로 (현재 자릿수 - 1)의 값을 이용하여 데이터를 쌓습니다. 마지막 수가 0일때와 9일때는 각 각 그 전자리 수가 1, 8일때만 계단수가 되므로 따로 계산을 해줍니다. 나머지 1~8일때는 각 각 (자신 - 1), (자신 + 1)의 값을 들고 오면 되므로 for문으로 따로 계산을 해주시면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include int n,cache[101][10],ret,mod=1000000000; in..

문제 출저 : https://www.acmicpc.net/problem/11057 풀이 : DP문제입니다. 0~9까지의 숫자를 사용하여 각 자릿수가 주어질 때 오르막 수의 갯수를 찾는 문제입니다. 00 이나 11 같이 앞의 숫자가 같아도 오르막 수로 취급되니 주의해주고 데이터를 쌓을 때 (자기 자릿수 -1)일때 0부터 자기자신 까지 나온 오르막 수를 다 더합니다. 예를 들어 자릿수가 2이고 마지막 수가 2이라 하면 (cache[2][2]) 자릿수가 1인 0,1,2로 오르막 수를 만들 수 있으니 자릿수가 2면서 마지막수가 2인 오르막수는 3개가 됩니다. 자릿수가 3이고 마지막 수가 2라고하면 0으로 끝나는 00로 1개, (cache[2][0]) 1로 끝나는 01 11로 2개, (cache[2][1]) 2로..

문제 출저 : https://www.acmicpc.net/problem/12865 풀이 : DP문제입니다. 무게와 물건의 2차원 공간에 Memoization을 적용하여 DP로 풀면 됩니다. 데이터를 쌓을 때 이전 까지 쌓아온 값과 이전 까지 쌓아온 값 중 현재 들어온 물건의 무게(w)를 뺀 후 가치(v)를 더한 값을 비교하여 큰것을 취득합니다. 한마디로 cache[i][j] = Max(v + cache[i - 1][j - w], cache[i - 1][j]) 가 됩니다. 저는 삼항연산자를 좋아하는 편이라 코드에는 Max대신 삼항연산자가 들어있습니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 #include int n,k,Max,cache[100][100001]..

문제 출저 : https://www.acmicpc.net/problem/1780 풀이 : 분할 정복 문제입니다. 만약 전체가 같은 수로 이루어 지지 않았다면 전체를 9구역으로 분할 한 후 계속 검사해 나갑니다. 저는 type 변수를 스위치 처럼 사용 하였습니다. 현재 분할 된 부분의 전체를 탐색하고 스위치가 켜지면 하나의 수로 채워진 종이가 아닌 경우이고 꺼져있으면 하나의 수로 채워진 종이라고 인식합니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 #include int n,arr[2187][2187],score[3]; void divide(int x,int y,int size) {..

문제 출저 : https://www.acmicpc.net/problem/1725 풀이 : 스택으로도 풀 수 있고, 분할 정복으로도 풀 수 있는 문제입니다. 스택으로는 아직 안 풀어 봐서 다음에 기회가 되면 올리도록 하고 분할 정복으로 설명하겠습니다. 이 문제는 분할 한 두 영역에 겹쳐서 최댓값이 존재 할 수도 있기 때문에 병합을 할 때 매번 중앙부터 시작해 양 옆으로 확장 해 나가면서 현재 구해진 값 과 중간 값 중 최댓값을 찾는 과정을 병행 해주어야 합니다. 그 과정은 중앙에서 부터 양옆으로 탐욕적으로 넓혀 나가시면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 3..

문제 출저 : https://www.acmicpc.net/problem/2447 풀이 : 분할 정복 문제입니다. 출력을 자세히 보면 *** * * *** 위 의 모양 처럼 중간 부분만 뻥 뚤린 형태를 유지하고 있음을 유추할 수 있습니다. 따라서 중간 부분만 출력 하지 않도록 9가지 구역으로 분할 후 정복하시면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 #include int n; char arr[7000][7000]; void divide(int y,int x,int size,int cnt) { if (size == 1||cnt==4) { arr[y][x] = cnt==4 ? '..

문제 출저 : https://www.acmicpc.net/problem/2805 풀이 : 이분 탐색 문제입니다. 절단기 높이의 최댓값은 나무 높이 들 중 최댓값이 됩니다. 기본적인 이분 탐색은 [2512] 예산 과 같으니 참고 하시면 감사하겠습니다. 그리고 나무의 최대 높이가 20억이니 꼭 결과값 저장할 때 long long int 같이 큰 정수 써주셔야합니다. 처음에 아무생각 없이 안썼다가 틀렸었습니다 .ㅠㅠ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 #include int n, m, arr[1000000], Max, result; void parametricSearch(int s, int e) { i..

문제 출저 : https://www.acmicpc.net/problem/2512 풀이 : 이분 탐색 문제입니다. 배정 될 수 있는 예산들 중 최댓값은 요청의 최댓값을 넘을 수 없기 때문에 e를 요청중 최댓값으로 설정합니다. mid를 요청 당 최대로 배정할 예산으로 두고 아래와 같이 계산합니다. 1. 요청 당 배정할 예산 >= 요청 : 요청만큼 배정 2. 요청 당 배정할 예산 < 요청 : 배정할 예산만큼 배정 그 후 현재 배정된 총 예산과 총 예산과 비교하고 아래와 같이 이분탐색을 실행합니다 1. 배정된 총 예산 총 예산 : parametricSearch(s, mid - 1); 배정된 총 예산이 총 예산보다 작다면 예산을 조금 더 배정 할 수 있다는 말이 되므로 예산을 더 늘려서 이분 탐색을 진행하고, 반..

문제 출저 : https://www.acmicpc.net/problem/9465 풀이 : DP문제입니다. 스티커를 떼면 변을 공유하는 모든 스티커는 사용 할 수 없으니 대각선 스티커만 보면 됩니다. 아래의 그림에서 60점 스티커를 뗀다고 가정했을때, 그 전에 점수를 쌓을 수 있는 경우는 20점과 100점을 뗐을 때 뿐입니다. 그럼 20점을 뗀다면 어떨까요? 그 전에 점수를 쌓을 수 있는 경우는 70점과 50점을 뗐을 때 뿐이겠죠. 따라서 쌓는 과정에서 값의 틀어짐이 없이 잘 쌓일 거라는 사실을 알 수 있습니다. 문제의 목표는 스티커 점수의 최댓값을 찾는 것이므로 두가지 경우 중 값이 더 큰 경우를 채택하면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20..