답은 알고리즘 뿐이야!

문제 출저 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18NaZqIt8CFAZN 풀이 : DP문제라고 해서 보긴 했는데 DP로 푸는방법이 떠오르진 않네요 ㅠㅠ 혹시 DP로 푸신분있으면 가르쳐 주시면 감사하겠습니다... 너무 야매로 푼거같아서 어떤 알고리즘으로 풀었다고 해야 할 지 모르겠네요... 일단 이 문제는 수나사와 암나사의 사이즈를 맞춰서 최대로 연결하는 문제입니다. 문제의 조건이 너무 불충분해서 제가 테스트 케이스로만 분석하여 수나사와 암나사의 최대 크기는 30, 금속 막대의 개수는 20개로 놓고 풀었습니다. 그다음 마찬가지로 조건이 너무 불충분 하여 두가지 가정을 하였습니다. 가정 1) ..

문제 출저 : https://www.acmicpc.net/problem/11726 풀이 : DP 문제 입니다. 1X2 타일과 2X1 타일로 2XN을 타일링 할 때 아래의 규칙대로 쌓으면 됩니다. 규칙 1) 1X2 타일을 2 X (i - 1) 타일링 한 것에 덧붙인다. 규칙 2) 2X1 타일을 2X2 타일로 만들어 2 X (i - 2) 타일링 한 것에 덧붙인다. 1 2 3 4 5 6 7 8 9 10 11 12 #include int n, cache[1001]; int main() { scanf("%d", &n); cache[1] = 1; cache[2] = 2; for (int i = 3; i

문제 출저 : https://www.acmicpc.net/problem/2193 풀이 : DP문제입니다. 이친수는 1) 첫번째 숫자는 0으로 시작할수 없다. 2) 1이 연속으로 나올 수 없다. 이 두가지 조건을 만족해야합니다. 따라서 데이터를 쌓을 때 2번 조건을 통해 얻어 낼 수 있는 아래의 규칙에 따라 쌓으시면 됩니다. 규칙 1) 현재 자릿수의 끝 수가 1인 이친수(cache[i][1])는 이전 자릿수의 끝 수가 0인 이친수(cache[i - 1][0])에서 밖에 만들 수 없다. 규칙 2) 현재 자릿수의 끝 수가 0인 이친수(cache[i][0])은 이전 자릿수의 끝 수가 0인 이친수(cache[i - 1][0])와 1인 이친수(cache[i - 1][1]) 둘 다에서 만들 수 있다. 1 2 3 4 ..

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

올해도 2차 예선 까지는 올라갔지만 역시 본선은 가지 못했다... 솔직히 2차 예선 3번까지 풀었을때 내심 기대는 했지만 떨어지고 나니 조금 아쉽다 빼애ㅐ애애앵 4번 완전탐색 돌린 사람들 본선 갔다던데 에이 그런 문제는 여기서 내지 않을꺼야! 라고 생각했던 나 자신을 패버리고 싶었다. 후우... 아쉽지만 내년에도 기회가 있으니 내년을 기약해야지... 풀이도 쓰고 싶었는데 오래되서 기억이 잘 안나는 관계로 패스~!

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