차근차근

0. 제목 백준 1931 회의실배정 BOJ 1931 회의실배정 C++ 1931 회의실배정 1. 문제 https://www.acmicpc.net/problem/1931 2. 풀이 최대 회의수를 구해야하기 때문에 시작시간을 기준으로 잡으면 안되고 종료시간을 기준으로 잡아야 한다. 시작시간을 기준으로 잡아버리면 (1, 10)이 있다고 할 때 (3, 5), (6, 8)이 들어갈 수 없기 때문에 최대수를 구할 수 없다. 따라서 종료시간으로 오름차순 정렬을 한 후, 만약 종료시간이 같다면 시작시간 기준으로 오름차순 정렬을 해준다. 현재 종료시간보다 나중에 있는 시작시간이 있다면 회의수인 cnt를 1증가시키고 현재 종료시간을 나중에 있는 종료시간으로 갱신해준다. 반복문의 모든 loop를 끝낸 이후의 cnt가 최대 회..

0. 제목 백준 1783 병든 나이트 BOJ 1783 병든 나이트 C++ 1783 병든 나이트 1. 문제 https://www.acmicpc.net/problem/1783 2. 풀이 경우의 수를 다음과 같이 따져보면 된다. 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 #include using namespace std; int main(int argc, const char * argv[]) { int N, M; int result = 1; cin >> N >> M; if(N == 1) result = 1; else if(N == 2){ result = min(4, (M+1)/2); }else if(N >= 3){ i..

0. 제목 백준 10610 30 BOJ 10610 30 C++ 10610 30 1. 문제 https://www.acmicpc.net/problem/10610 2. 풀이 30의 배수가 되려면 3의 배수이면서 10의 배수여야한다. 10의 배수이려면 마지막에 0이 반드시 나와야 하고 3의 배수이려면 각 자리 수의 합이 3으로 나누어 떨어져야 한다. 그리고 문제에서 N이 최대 100000개의 숫자로 구성되어 있다고 하여 문자열로 입력을 받았다. 먼저 입력값에 0이 포함되어 있는지 확인하고 포함되어 있는 것들의 자리수 합을 구한다. 자리수가 3으로 나누어 떨어지면 내림차순을 하고 정답을 출력한다. 조건에 맞지 않으면 -1을 출력한다. 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16..

0. 제목 백준 2875 대회 or 인턴 BOJ 2875 대회 or 인턴 C++ 2875 대회 or 인턴 1. 문제 https://www.acmicpc.net/problem/2875 2. 풀이 그리디 알고리즘을 사용하였다. 2명의 여학생과 1명의 남학생이 팀을 만들어야 하고 K명이 인턴쉽에 참여해야 한다. K명이 빠져야 하므로 여학생, 남학생에서 합하여 K명 만큼 모든 경우의 수대로 뺀다. 여학생 2명과 남학생 1명이므로 위에서 뺀 값을 각각 2와 1로 나눈다. 두 값중 작은 값이 만들어질 수 있는 팀의 수가 된다. 최대의 팀 수를 구해야 하므로 최대값과 만들어진 팀을 비교하면서 최대값을 갱신하고 최종 결과가 답이 된다. 다음과 같은 방식으로도 답을 구할 수 있다. min(N/2, M, (N+M-K)/3..

0. 제목 백준 11047 동전 0 BOJ 11047 동전 0 C++ 11047 동전 0 1. 문제 https://www.acmicpc.net/problem/11047 2. 풀이 그리디 알고리즘을 사용하였다. 그리디 알고리즘(욕심쟁이 알고리즘, Greedy Algorithm)이란 "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"라는 모토를 가지는 알고리즘 설계 기법이다. 동전의 가치가 오름차순으로 주어지기 때문에 가치가 큰 동전부터 차례대로 나눈다. 몫만큼 cnt에 더해주고 K를 나머지로 갱신해준다. 그렇게 모든 동전에 대해서 K/value[i]의 값이 0이 아닌동안 반복하면 누적된 cnt가 정답이다. 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1..