bbearcookie
- All
- algorithm
- react
- issue
[백준 1931] 회의실 배정
문제 https://www.acmicpc.net/problem/1931 아이디어 기본적으로 종료 시간이 빠른 회의를 먼저 진행해야 최대한 많은 회의를 할 수 있는 가능성이 있기에 종료 시간을 기준으로 정렬을 해야 한다. 그런데, 종료 시간이 같다면 시작 시간이 더 빠른 회의를 먼저 진행해야 한다. 만약 (7, 8) (6, 8)의 두 회의가 있다면 시작 시…
[백준 11399] ATM
문제 https://www.acmicpc.net/problem/11399 아이디어 소요 시간이 적게 걸리는 사람부터 진행해야 전체 사람이 기다려야 하는 시간이 줄어들게 되고 전체 대기시간의 총합이 최소가 되므로, 소요 시간이 적은 사람부터 은행 업무를 처리하고 해당 사람들이 대기해야 하는 시간을 합하여 출력한다. 소스코드
[백준 11047] 동전 0
문제 https://www.acmicpc.net/problem/11047 아이디어 동전의 갯수를 최소로 하기 위해서는 가장 큰 동전을 우선적으로 사용해야 한다. 그렇기에 큰 동전부터 사용하고, 잔액보다 큰 동전을 만난다면 그 다음으로 큰 동전을 사용하는 과정을 반복하면 된다. 참고로 i번째 동전은 반드시 i-1번째 동전의 배수이기 때문에 이러한 그리디 알…
[백준 12865] 평범한 배낭
문제 https://www.acmicpc.net/problem/12865 아이디어 각각의 물품에 대해서 배낭의 용량을 증가시키면서 특정 용량일 때 얼마만큼의 가치가 들어가는지를 계산하여 저장하고, 그 저장된 결과를 다음 물품을 계산할 때 참고하여 사용하면 된다. 각 물품의 특정 배낭 용량에 대해서 얼마만큼의 가치가 들어가는지를 기록하는 2차원 배열 dp를…
[백준 2156] 포도주 시식
문제 https://www.acmicpc.net/problem/2156 아이디어 이전에 풀었던 계단 오르기와 유사한 문제이다. 다만, 계단 오르기는 한 계단을 밟으면서 이어서 다음 계단으로 오를수 있기에 반드시 해당 계단을 밟은 상태를 가정해서 계산해야 했지만, 이 문제는 현재 선택한 포도주를 반드시 마시지 않아도 되기에 그 점을 고려해서 계산해야 한다.…
[백준 2579] 계단 오르기
문제 https://www.acmicpc.net/problem/2579 아이디어 각 계단까지의 합을 기록해두고 점차 다음 계단으로 올라가면서 더 높은 합이 나오도록 하면 된다. 먼저 1번째 계단까지의 합은 무조건 1번째 계단의 점수가 된다. 2번째 계단까지의 합도 무조건 1번째 계단의 점수+2번째 계단의 점수가 된다. 그런데 세 개의 계단을 연달아서 밟을…
[백준 1912] 연속합
문제 https://www.acmicpc.net/problem/1912 아이디어 합을 기록하는 변수를 0으로, 최대합을 기록하는 변수를 존재할 수 있는 최소값 으로 설정한다. 수열의 모든 값을 순회하면서 연속합을 계산한다. 만약 연속합이 음수라면, 이후의 값과 더했을 때 값을 감소시키는 효과만 있으므로 연속합을 버리고 다시 0으로 설정한다. 만약 연속합이…
[백준 1149] RGB거리
문제 https://www.acmicpc.net/problem/1149 아이디어 모든 집에 대해서 특정 색상으로 색칠했을 때 필요한 비용을 기억하는 2차원 배열을 정의한다. 맨 첫번째 집은 그 집을 색칠하는데 드는 비용 자체가 곧 필요한 비용이 되므로, cost 배열에 그 값을 초기화한다. 이후에 집을 순회하면서 각각 색칠하는데 드는 비용을 계산하고 기록…
[백준 1654] 랜선 자르기
문제 https://www.acmicpc.net/problem/1654 아이디어 자르려는 랜선의 길이를 가지고 조정하면서 이진 탐색을 하면 되는 문제이다. 가장 긴 사이즈와 가장 짧은 사이즈의 중간 크기로 잘랐을 때 케이블이 부족하다면 랜선을 더 짧게 잘라야 한다. 반면에, 케이블이 남는다면 더 길게 잘라도 되므로 더 길게 잘랐을 때 케이블의 갯수가 어떻…
[백준 10816] 숫자 카드 2
문제 https://www.acmicpc.net/problem/10816 아이디어 1 (해쉬 이용) 상근이가 가지고 있는 숫자 카드를 한번씩 순회하면서, 같은 카드의 갯수를 세고 해쉬에 저장한다. 상근이가 몇 개나 가지고 있는 숫자 카드인지를 해쉬 맵에서 꺼내서 확인한다. 소스코드 1 아이디어 2 (이분탐색 이용) 상근이가 가지고 있는 숫자 카드를 오름차…