[백준] 14501번 퇴사 C++ 문제풀이

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 문제 풀이 완전탐색 문제여서 모든 경우를 고려했다. 그 날의 상담을 수락하는 경우와 그 날의 상담을 하지 않고 그냥 다음 날로 넘어가는 2가지 경우로 나누어 진행했다. DFS를 이용해 상담을 수락하는 경우는 상담이 끝나는 다음 날로 이동하고, 아닌 경우는 다음 날로 이동하게 코드를 작성했다. 소스 코드 #include using namespace std; int money[21] = { 0 }; int day[21] = { 0 }; int N; int max_num = 0; void dfs(int d, int m) { if (d > ..

• format_list_bulleted 알고리즘
• · 2023. 8. 11.

[백준] 2503번 숫자 야구 C++ 문제풀이

https://www.acmicpc.net/problem/2503 2503번: 숫자 야구 첫째 줄에는 민혁이가 영수에게 몇 번이나 질문을 했는지를 나타내는 1 이상 100 이하의 자연수 N이 주어진다. 이어지는 N개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트 www.acmicpc.net 문제 풀이 두 수의 자리수를 비교하는 경우 string으로 변환해서 비교하는게 편해 string으로 변환한 후 자리수를 비교했다. '1에서 9까지의 서로 다른 숫자 세 개로 구성된 세 자리 수'라는 조건이 있어 0이 있거나 중복된 수는 고려하지 않고 완전탐색 방식으로 답을 구했다. 소스 코드 #include #include ; using namespace std; string num[101]; i..

• format_list_bulleted 알고리즘
• · 2023. 8. 10.

[백준] 1300번 K번째 수 C++ 문제풀이

https://www.acmicpc.net/problem/1300 문제 풀이 처음 문제 풀이에서는 Symmetric 행렬의 특성이 뭐가 있나 고민해봤는데 딱히 결론이 나오지 않았다... 다른 분들의 블로그를 참고해보니 이분검색으로 Mid 보다 작은 숫자들의 수를 세어서 그 합이 K보다 크면 작은 쪽을, 그 합이 K보다 작으면 mid보다 큰쪽을 검색하는 식으로 진행하는 문제였다. 소스 코드 #include using namespace std; int main() { long long N, K; cin >> N >> K; long long max_idx = K; long long min_idx = 1; long long result = 0; while (min_idx

• format_list_bulleted 알고리즘
• · 2023. 8. 9.

[백준] 2108번 통계학 C++ 문제풀이

https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 문제 풀이 이 문제 풀 때 어려웠던 점은 산술평균과 최빈값을 구하는 과정이었던 것 같다. 산술 평균의 경우에는 float로 바꾼 후 연산하고 cmath의 round를 이용해 값을 구했다. 최빈값 같은 경우에는 숫자가 나온 횟수를 저장하는 cnt배열을 만들어 숫자를 저장한 후 값들을 비교해 최빈값을 구했다. 소스 코드 #include #include #include #include using namespace s..

• format_list_bulleted 알고리즘
• · 2023. 8. 9.

[백준] 1339번 단어 수학 C++ 문제풀이

https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 문제 풀이 맨 처음에는 자릿수마다의 알파벳을 저장해 완탐형식으로 하려 했는데 잘되지 않았다. 그래서 알파벳 별로 자릿수들의 합을 이용해 문제를 해결했다 예를 들어 1번 예시인 AAA, AAA 인 경우에는 alpha[0] = 222가 들어가는 형식이다. 아무튼 이런 방법으로 합이 큰 값들부터 정렬해서 9부터 차례로 곱해주었다. 소스코드 #include #include #include #incl..

• format_list_bulleted 알고리즘
• · 2023. 8. 7.

[백준] 9663번 N-Queen C++ 문제풀이

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 풀이 백트래킹을 이용해 문제를 해결했다. Promising 이란 함수를 만들어서 체스판에 놓여진 위치가 유망한지 아닌지를 판단했다. Promising에서는 같은 column인지, 같은 대각에 있는지를 확인했다 같은 행인것을 확인 안 한 것은 행마다 하나의 Queen을 놓는 식으로 코드를 작성해 같은 행인지에 대해서는 확인할 필요가 없다. 알고리즘 수업때 배운 내용이여서 큰 문제 없이 코드를 작성했다. 소스코..

• format_list_bulleted 알고리즘
• · 2023. 8. 6.