C++
-
알고리즘: 백준 11052번 카드 구매하기(feat.c++)알고리즘/백준(BaekJoon) 2020. 8. 23. 18:13
백준 11052번 링크입니다. 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 다이나믹 프로그래밍을 이용하면 쉽게 해결할 수 있다. 우선 코딩하기 전에 dp[n]을 말로 정의하는 게 중요하다. dp[n] = n개의 카드를 구매했을 때 최댓값 라고 하자 dp[n]을 구하기 위해서는 다음과 같은 과정을 거친다. (편의상 k번째 dp[n]을 dpk[n]라고 하자) dp1[n] = dp[n - 1] + packs[1] dp2[n] = dp[n - 2] + packs[2] dp3[n] = dp[n - 3] + packs[3] ..
-
알고리즘: 백준 1010번 다리놓기 (feat. c++)알고리즘/백준(BaekJoon) 2020. 8. 18. 19:00
백준 1010번 링크입니다. 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net n개 중에 r개를 고르면 되므로 nCr을 사용하면 간단하다...고 생각했지만 아니였다. 팩토리얼을 다이나믹 프로그래밍으로 구해서 콤비네이션하려 했지만 long long 자료형을 써도 넘어가버려서 다이나믹 프로그래밍과 재귀함수를 이용하였다. nCr = n-1Cr-1 + n-1Cr 을 이용해서 recursive form을 만들어 해결하였다. #include using namespace std; int cache[30][30]; // 다이..
-
알고리즘: 백준 1018번 체스판 다시칠하기(feat. c++)알고리즘/백준(BaekJoon) 2020. 8. 18. 16:28
백준 1018번 링크입니다. 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net B로 시작하는 8 x 8 완성된 체스판을 chess1 W로 시작하는 8 x 8 완성된 체스판을 chess2 내가 입력받을 잘못된 체스판을 wrong_chess라고 하자 wrong_chess의 행과 열을 변화시켜 가면서 chess1과 chess2와 비교한다. chess1과 비교했을 때 잘못된 값의 갯수 = wrong_count1 chess2과 비교했을 때 잘못된 값의 갯수 = wrong_count2일때 두 값중에 더 작은 값을 ..
-
알고리즘: 백준 1037번 약수(feat. c++)알고리즘/백준(BaekJoon) 2020. 8. 18. 14:35
백준 1037번 링크입니다. 1037번: 약수 첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되� www.acmicpc.net 방법 1 #include using namespace std; int main() { int n; int x; int max = -1; int min = 1000000; cin >> n; for (int i = 0; i > x; if (max x) { min = x; } } int answer = min * max; cout n; for (int..