반응형 브루트포스4 [백준 19942] 2020 정올 1차 중등부 "다이어트" 문제 출처 : https://www.acmicpc.net/problem/19942 19942번: 다이어트 식재료 N개 중에서 몇 개를 선택해서 이들의 영양분(단백질, 탄수화물, 지방, 비타민)이 일정 이상이 되어야 한다. 아래 표에 제시된 6가지의 식재료 중에서 몇 개를 선택해서 이들의 영양분의 각 www.acmicpc.net 이 문제는 2020년 정보올림피아드 1차 중등부 2번 문제 입니다. 문제 이해하기 단백질, 지방, 탄수화물, 비타민의 최소 영양성분을 넘어서는 최소 가격을 찾으면 되는 문제 입니다. N의 크기가 15로 비교적 작기 때문에 브루트 포스나 백트래킹으로 쉽게 결과를 찾을 수 있습니다. 백트래킹을 통해 문제를 해결해 보겠습니다. 백트래킹에 대해 잘 모른다면 아래 링크를 통해 백트래킹 기법.. 2024. 3. 3. [백준 17610] 2019 정올 1차 중등부 "양팔저울" 문제 출처 : https://www.acmicpc.net/problem/17610 17610번: 양팔저울 무게가 서로 다른 k개의 추와 빈 그릇이 있다. 모든 추의 무게는 정수이고, 그릇의 무게는 0으로 간주한다. 양팔저울을 한 번만 이용하여 원하는 무게의 물을 그릇에 담고자 한다. 주어진 모든 추 www.acmicpc.net 이 문제는 2019년 정보 올림피아드 1차 중등부 1번 문제 입니다. 양팔 저울을 가지고 만들 수 있는 모든 무게를 찾아 불가능한 경우의 수를 출력하는 문제 입니다. 따라서 1부터 모든 추의 무게를 따져가며 만들 수 있는지, 없는지 확인해야 합니다. 이런 문제는 DP를 통해 풀 수 있습니다. DP의 배낭 문제를 통해 이 문제의 해결 방안을 생각해 볼 수 있습니다. 경우의 수를 따져.. 2024. 2. 23. [백준 15686] 치킨 배달 문제 출처 : https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 치킨을 배달할 수 있는 치킨 거리가 가장 짧아지는 경우를 구하는 문제 입니다. 여기서 거리를 구하는 방식은 맨하탄 거리(Manhattan Distance)를 구하는 공식 입니다. 좌표간의 거리를 구하는 방식 중 하나로 간단한 계산으로 거리를 구할 수 있습니다. 알고리즘 지도의 크기 N의 최대는 50이고 치킨 집의 개수의 최대는 13입니다. 이정도의 크기라면 브루.. 2023. 9. 27. [백준 10972] 다음 순열 문제 출처 : https://www.acmicpc.net/problem/10972 10972번: 다음 순열 첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net permutations 함수를 사용하면 쉽게 해결 가능한 문제로 보입니다. permutations에 대해 잘 모른다면 다빈치코딩 알고리즘 브루트포스를 확인 바랍니다. 하지만 막상 해결이 쉽지 않습니다. 무작정 해보기 for문을 통해 순열들을 호출해서 입력된 배열과 비교하여 같은 것이 나올 때까지 찾습니다. 같은 것이 나오면 마지막 순열이면 -1을 출력하고, 아니면 다음 순열을 출력하면 됩니다. 하지만 막상 이렇게 풀면 시간초과가 됩니다. 시간.. 2023. 9. 4. 이전 1 다음 반응형
