본문 바로가기

Algorithm/Brute Force

BaekJoon 14501 퇴사 2019. 2. 3. Link https://www.acmicpc.net/problem/14501 소스코드 1984 KB / 0 ms 출처 Baekjoon 언어 C++ 17 분류 다이나믹 프로그래밍, 브루트 포스 설명 정말 부러운 상황에 있는 백준이가 퇴사를 하려한다, 상담 계획이 주어져 있을 때, 최대로 돈을 많이 벌 수 있는 금액을 출력해주자. 백준이가 퇴사 하기 전까지 최대한 많은 상담을 해야한다. 백준이가 돈을 더 벌기 위해서 일을 일부러 건너 뛰는 경우도 존재 한다. 또한 일을 하는 경우에 자신의 퇴사일이 지나는 경우에는 일을 받지 않아야 한다. 돈을 더 벌기 위해서 일을 하지 않아야 하는 경우와 퇴사일이 지나는 경우를 포함하면 총 3가지 경우가 존재한다. DP로 구현하는 방법도 있지만 이번에는 브루트 포스를 이용해..
BaekJoon 2309 일곱 난쟁이 2019. 2. 3. Link https://www.acmicpc.net/problem/2309 소스결과 1988 KB / 0 ms 출처 Baekjoon, KOI 2004 초등부 1번 언어 C++ 17 분류 브루트 포스 설명 아홉 명의 난쟁이 중 일곱명을 선택해 난쟁이의 키가 100이되는 경우에 난쟁이의 키를 오름차순으로 출력하자. 오름차순으로 출력 하기 위해 9명의 난쟁이를 먼저 오름차순으로 정렬하자. 9명중에 7명을 조합하는 재귀 함수를 만든다. 합이 100이면 출력하자. 최종 경우에 합을 가지고만 판단하기에 앞서 누가 선태 되었는지 확인 할 수 없기에 누가 선택 됬는지 기억해줄 배열이 하나 필요하다. 알고리즘 1. 입력되는 9명의 난쟁이를 오름차순으로 정렬한다. 2. 9명 중 7명을 선택하는 조합 재귀함수를 만든다. 2..
BaekJoon 1107 리모컨 2019. 1. 15. Link https://www.acmicpc.net/problem/1107 소스결과 2084KB 12 ms 출처 Baekjoon 언어 C++ 17 분류 브루트포스 설명 어떤 멍청이가 버튼을 너무 세게 누르는 바람에 버튼이 고장나서 내가 원하는 채널로 갈때 내가 버튼을 몇번 눌러야 하는지 계산 하는 문제 왜 고장을 낸건지 너무 화가난다. 처음으로 백준 게시판에 안된다고 반례 찾아달라고 질문 올린 문제, 테스트케이스만 30개 이상 돌려본거 같다. 접근을 3가지 방법으로 해야한다 1. 현재 채널에서 목표 채널까지 + , - 을 눌러서 최소로 가는 경우 2. 목표 채널보다 작으면서 최대인 경우 3. 목표 채널보다 크면서 최소인 경우 3가지 방법중에 최소인 경우를 구해야 한다. 또한 0000 의 경우에는 0을 한..
BaekJoon 14888 연산자 끼워넣기 2019. 1. 15. Link https://www.acmicpc.net/problem/14888 소스결과 1988 KB / 0 ms 출처 Baekjoon 언어 C++ 17 설명 수 사이에 연산자를 넣어 최대 최소가 되는 경우를 찾아내는 문제 수는 신경쓰지 않고 연산자를 할당하는 부분에 신경을 기울이면 된다. 또한 연산자의 개수가 정해져 있기 때문에 현재까지 몇개를 할당 해 줬는지 기억을 해줄 필요가 있다 연산자가 n-1개가 아니라 n개라면 맨 앞에 -를 넣는 경우를 생각 해야 하지만 현재 문제는 n-1 개 이기 때문에 고려하지 않아도 된다. 계산식의 우선순위가 없다는 점이 문제의 난이도를 낮춘다. 유의 할 점은 이번 연산자가 / 일때 분모가 0이 되는 경우는 제외해서 연산을 시켜야 한다. 또한 값을 최대 최솟값이 doubl..
BaekJoon 1213 팰린드롬 만들기 2019. 1. 10. Link https://www.acmicpc.net/problem/1213 소스결과 1988KB / 0 ms 출처 Backjoon 언어 C++ 17 분류 브루트포스(Brute Force), 정렬(Sorting) 연관 검색어 1213 C++, BOJ 1213 C++ 설명 주어진 단어를 팰린드롬으로 바꿀 수 있는지에 대한 문제 팰린드롬이란 ? 위키백과 - 회문(Palindrome) 백준 문제 종류가 브루트포스이지만 풀고나서 채점결과를 보니 막상 그렇게 구현한사람은 찾기 힘들다. 정렬로 보면 Counting Sort에 속하기는 하지만 실질적으로 정렬을 하지는 않으니 정렬도 애매하다고 생각된다. 길이가 홀수인 경우, 짝수인 경우로 분류해서 해결하고 불가능한 경우가 명확하기 때문에 불가능한 경우를 제한다면 정답은..
BaekJoon 15683 감시 2019. 1. 9. Link https://www.acmicpc.net/problem/15683 소스결과 1988KB 36ms 출처 Backjoon 언어 C++17 설명 5 종류의 최대 8개의 감시카메라가 최대 8 x 8의 정사각형 방을 감시하는데 최소 사각지대를 구하는 문제이다. 문제 내용도 간단하고 무엇보다 설명이 자세하게 잘 되어있던 문제 예제 또한 많았기에 예제가 정상적으로 전부 돌아간다면 반례는 크게 생각을 하지 않아도 될 것 같다. 재귀적 구조로 순열을 구현해 각 상황에 맞게 사각지대를 확인하는 방식으로 구현했다. 원래 맵 자체를 건드리면 안되기에 8 by 8 bool map을 매번 새로 생성해 결과를 확인 했는데 최악의 경우 400만번이 넘는 경우가 나와 시간초과를 예상했으나 무난하게 잘 돌아갔다. 문제 자체를..
BaekJoon 1065 한수 2018. 12. 28. Link : https://www.acmicpc.net/problem/1065 소스 결과 : 1984 KB / 0 ms 출처 : BackJoon 설명 생각보다 쉬운 문제 일단 범위가 자연수 한정에 1000 이하 이지만 실질적으로 1 ~ 99 까지는 무조건 등차수열이고 1000은 등차수열이 아니니 100 ~ 999 까지만 계산하면 되는 문제였다. 소스코드 #include using namespace std; int main() { int n; int count = 0; cin >> n; if (n == 1000) // 1000 is not arithmetic sequence n = 999; if (n < 100) // under 100 is arithmetic sequence count = n; else ..
BaekJoon 7568 덩치 2018. 12. 27. Link : https://www.acmicpc.net/problem/7568 소스 결과 : 1984 KB / 0 ms 출처 : BackJoon / 한국정보올림피아드시, 도지역본선 지역본선 2013 초등부 2번 소스코드 #include using namespace std; int weight[50]; int height[50]; int mRank[50]; int main() { int n; cin >> n; for (int i = 0; i > weight[i] >> height[i]; for (int i = 0; i weight[i] && height..

티스토리툴바