답은 알고리즘 뿐이야!

문제 출저 : 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) {..