본문 바로가기

c++831

[백준] 1497번 : 기타콘서트 (C++) 1497번 : 기타콘서트 문제) 강토는 Day Of Mourning의 기타리스트로, 다가오는 공연을 준비하고 있다. 어느 날 강토의 집에 도둑이 들어서 기타를 모두 도둑맞고 말았다. 기타를 사야 한다. 강토는 공연 때 연주할 노래의 목록을 뽑아 놓았다. 하지만, 하나의 기타로 모든 곡을 연주할 수는 없다. 어떤 기타는 어떤 곡을 연주할 때, 이상한 소리가 나기 때문이다. 항상 완벽을 추구하는 강토는 이런 일을 용납하지 않는다. 최대한 많은 곡을 제대로 연주하려고 할 때, 필요한 기타의 최소 개수를 구하는 프로그램을 작성하시오. 예를 들어, GIBSON으로 1, 2, 3번 곡을 제대로 연주할 수 있고, FENDER로 1, 2, 5번 곡을 제대로 연주할 수 있고, EPIPHONE으로 4, 5번 곡을 제대로 .. 2024. 2. 24.
[백준] 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.

티스토리툴바