본문 바로가기

알고리즘4

[백준] 1041번 : 주사위 (C++) https://www.acmicpc.net/problem/1041 1041번: 주사위 첫째 줄에 N이 주어진다. 둘째 줄에 주사위에 쓰여 있는 수가 주어진다. 위의 그림에서 A, B, C, D, E, F에 쓰여 있는 수가 차례대로 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, 쓰여 있는 수 www.acmicpc.net 주사위의 6개의 눈과 N을 입력받으면, 해당 주사위로 이루어진 N×N×N크기의 정육면체의 5개의 면에 쓰여 있는 수의 합의 최솟값을 출력하는 문제이다. 처음에는 3면이 보이는 주사위 갯수, 2면이 보이는 주사위 갯수, 1면이 보이는 주사위 갯수를 구하고, 각각 주사위의 3면,2면,1면의 최소합을 구해 곱하면 되는줄 알았다. 운이 좋게도, 테스트 케이스는 다 통과했지만 "틀렸.. 2021. 8. 22.
[백준] 1793번:타일링 (C++) https://www.acmicpc.net/problem/1793 1793번: 타일링 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 숫자 0 ≤ n ≤ 250이 주어진다. www.acmicpc.net 이 문제 점화식은 간단하다. 2x1칸이 오른쪽에 추가 되었을때, 새롭게 타일을 채우는 방법은 총 3가지 케이스이다. 추가 후 현재 타일이 2xN 이라고 할때, 1. 기존 2x(N-1) 타일 + 1개의 2x1 타일 2. 기존 2x(N-2) 타일 + 2개의 1x2 타일 3. 기존 2x(N-2) 타일 + 1개의 2X2 타일 즉, dp[N]가 2 X N 타일을 채우는 방법의 수라고 할때 점화식은 다음과 같다. dp[i] = dp[i-1] + dp[i-2] + dp[.. 2021. 8. 21.
[백준] 10819번 : 차이를 최대로 (C++) https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 이 문제는 배열을 입력 받아 순서를 적절히 바꿔 |A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]| 값을 최대로 만드는 것이었다. 처음에는 DP문제인줄 알았으나 해결방법이 떠오르지 않았다. 생각을 해보니 N이 최대 8이기 때문에 완전 탐색, 즉 브루트포스로 구현이 가능할 것 같았다. 백트래킹을 통해 주어진 배열로 만들수 있는 모든 케이스에 대한 각 결과값을 계산하.. 2021. 8. 19.
[백준] 2251번 : 물통 (C++) https://www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net 이 문제는 BFS(너비우선탐색)으로 풀었다. 우선, 3가지 물통으로 물을 부을 수 있는 방법은 총 6가지로 각 물통을 0,1,2라고 했을 때 다음과 같다. 0 -> 1 0 -> 2 1 -> 0 1 -> 2 2 -> 0 2 -> 1 From[i] -> To[i] 핵심은 물의 총 양은 고정되어 있고 맨 처음 세번째 입력으로 주어지기 때문에, 첫번째 물통과 두번째 물통의 물의 양만 .. 2021. 8. 19.

티스토리툴바