백트래킹61 [백준] 16945번 : 매직 스퀘어로 변경하기 (C++) 16945번 : 매직 스퀘어로 변경하기 문제) 1부터 N2까지의 수가 하나씩 채워져 있는 크기가 N×N인 배열이 있고, 이 배열의 모든 행, 열, 길이가 N인 대각선의 합이 모두 같을 때, 매직 스퀘어라고 한다. 크기가 3×3인 배열 A가 주어졌을 때, 이 배열을 매직 스퀘어로 변경하려고 한다. 한 칸에 있는 수 a를 b로 변경하는 비용은 |a - b| 이다. 예를 들어, 아래와 같은 경우를 살펴보자. 5 3 4 1 5 8 6 4 2 이 배열의 수를 아래와 같이 변경하면 매직 스퀘어가 되고, 비용은 |5 - 8| + |8 - 9| + |4 - 7| = 7 이다. 8 3 4 1 5 9 6 7 2 3×3 크기의 배열 A가 주어졌을 때, 이 배열을 매직 스퀘어로 변경하는 비용의 최솟값을 구해보자. 배열 A는 .. 2024. 2. 24. [백준] 2961번 : 도영이가 만든 맛있는 음식 (C++) 2961번 : 도영이가 만든 맛있는 음식 문제) 도영이는 짜파구리 요리사로 명성을 날렸었다. 이번에는 이전에 없었던 새로운 요리에 도전을 해보려고 한다. 지금 도영이의 앞에는 재료가 N개 있다. 도영이는 각 재료의 신맛 S와 쓴맛 B를 알고 있다. 여러 재료를 이용해서 요리할 때, 그 음식의 신맛은 사용한 재료의 신맛의 곱이고, 쓴맛은 합이다. 시거나 쓴 음식을 좋아하는 사람은 많지 않다. 도영이는 재료를 적절히 섞어서 요리의 신맛과 쓴맛의 차이를 작게 만들려고 한다. 또, 물을 요리라고 할 수는 없기 때문에, 재료는 적어도 하나 사용해야 한다. 재료의 신맛과 쓴맛이 주어졌을 때, 신맛과 쓴맛의 차이가 가장 작은 요리를 만드는 프로그램을 작성하시오. 입력 : 첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10.. 2024. 2. 24. [알고리즘] 백트래킹 2 (Backtracking) 개인 공부 후 자료를 남겨놓기 위한 목적이므로, 생략되거나 오류가 있을 수 있음을 알립니다. 해당 필기는 2024.02.15 - [Develop/algorithm] - [알고리즘] 백트래킹 (Backtracking) 에서 이어집니다. 목차 1. 기존 백트래킹 변형 2. 2차원 백트래킹 1. 기존 백트래킹 변형 앞선 포스팅에서 우리는 3가지 형태의 템플릿을 보았다. 이번엔 이를 다른 형태로 변환해 사용해보도록 하자. 이전의 백트래킹(1, 2, 3 템플릿)은 cur가 채운 개수 기준이었다. 새로운 백트래킹 형식은 다음과 같다. 여기서의 cur는 여태까지 본 원소의 개수, cnt는 고른 원소의 개수가 된다. 이를 실제 문제풀이 형식에 맞추어 변형해보면 다음과 같이 바뀐다. 만약 위 코드를 응용해, 3개 이하의.. 2024. 2. 23. [백준] 25602번 : 캔 주기 (C++) 25602번 : 캔 주기 문제) 랑이 집사는 자신의 고양이 랑이와 메리 둘에게 매일 아침 캔을 정확히 하나씩 준다. 랑이 집사가 가진 캔의 종류는 N가지로, 집사는 i번째 캔을 A[i]개 갖고 있다. 랑이와 메리는 입맛이 까다롭고 변덕이 심해서 매일 각 캔에 대한 만족도가 다르다. i번째 날 랑이가 j번째 캔을 먹었을 때 만족도는 R[i][j], i번째 날 메리가 j번째 캔을 먹었을 때 만족도는 M[i][j]로 나타난다. 자연수 N과 A, R, M 배열이 주어질 때, 랑이 집사가 현재 가진 캔으로 K일동안 랑이와 메리에게 하루에 하나의 캔을 줘서 얻을 수 있는 만족도의 합의 최댓값을 구하는 프로그램을 작성하시오. 입력 : 출력 : 랑이와 메리의 만족도의 합의 최댓값을 출력한다. 풀이) 1 2 3 4 5 .. 2024. 2. 20. 이전 1 2 3 4 5 ··· 16 다음
