승코딩당당당

문제[C++] 백준 1946: 신입 사원 SILVER 1https://www.acmicpc.net/problem/1946 접근 방법이 문제는 지원자들의 서류 성적, 면접 성적이 주어졌을 때,“두 성적 모두 다른 지원자에게 밀리는 경우 탈락”이라는 기준으로 합격할 수 있는 최대 인원 수를 구하는 문제다. 처음에는 각 지원자에 대해 “이 사람보다 서류, 면접 둘 다 더 좋은 사람이 있는지”를 2중 for문으로 전부 비교하는 방식으로 생각했다. 하지만 이렇게 하면 지원자 수 N이 클 때 O(N²) 가 되어 시간 초과가 발생했다.. 그래서 접근을 바꿔서,서류 성적 기준으로 오름차순 정렬을 하고서류 1등은 무조건 합격이므로 기준으로 삼고,뒤에서부터는 지금까지 본 면접 성적의 최솟값(Min)을 계속 갱신하면서,현..

문제[C++] 백준 5585: 거스름돈 BRONZE 2https://www.acmicpc.net/problem/5585 접근 방법이 문제는 1000엔을 냈을 때 거슬러 받아야 할 금액이 주어지면,동전의 개수를 최소로 사용해 거스름돈을 만드는 문제이다. 사용 가능한 동전은 500, 100, 50, 10, 5, 1 엔으로 이미 큰 값부터 작은 값까지 정렬된 상태이며,이 동전 체계에서는 그리디 알고리즘이 항상 최적해를 보장한다. 그래서 다음과 같은 전략을 사용했다.입력받은 금액을 1000엔에서 빼서 거스름돈(money) 을 계산한다.가장 큰 동전부터 차례대로 확인하면서,해당 동전을 최대한 많이 사용한다.남은 금액은 나머지 연산으로 갱신한다.사용한 동전의 개수를 누적해 최종 결과로 출력한다. 구현 시 주의할 ..

문제[C++] 백준 22864: 피로도 BRONZE 2https://www.acmicpc.net/problem/22864 접근 방법이 문제는 하루 24시간 동안 일을 할지, 쉴지 선택하면서피로도 한도(m)를 넘지 않도록 하면서 최대한 일을 많이 하는 시뮬레이션 문제다. 한 시간 일하면피로도 a 증가일량 b만큼 증가한 시간 쉬면피로도 c만큼 감소 (단, 0 미만으로는 내려가지 않음)피로도가 m을 초과하면 더 이상 일할 수 없다. 그래서 하루 24시간을 1시간 단위로 반복하면서,현재 피로도 now에 a를 더했을 때 m 이하여야 일을 할 수 있다.now + a 아니면 → 쉬기일을 한 시간은 cnt를 1 증가모든 시간이 끝나면 cnt * b가 총 일량이 된다.즉, 그리디하게 “가능하면 무조건 일하고, 아니면 ..

문제[C++] 백준 1541: 잃어버린 괄호 SILVER 2https://www.acmicpc.net/problem/1541 접근 방법이 문제는 주어진 식에 괄호를 적절히 쳐서 결과 값을 최소로 만드는 문제다.핵심 아이디어는 정말 단순하다.한 번 - 가 등장한 이후에는, 그 뒤에 나오는 모든 수를 한 덩어리로 묶어서 한 번에 빼면 전체 값을 최소로 만들 수 있다. 예를 들어,55-50+40 이라면→ 55-(50+40) 으로 묶는 게 최솟값즉, 첫 번째 -를 기준으로 식을 나누고,첫 번째 덩어리는 그대로 더하고두 번째 덩어리부터는 “+로 묶인 값들을 모두 더한 뒤” 통째로 빼면 된다. 상세 아이디어1. split 함수로 문자열 자르기먼저, 문자열을 특정 문자 기준으로 잘라주는 split 함수를 만들었다...

문제[C++] 백준 1744: 수 묶기 GOLD 4https://www.acmicpc.net/problem/1744 접근 방법이 문제는 주어진 정수들을 적절히 묶어서(곱하거나 더해서) 전체 합의 최댓값을 만드는 문제다.핵심 아이디어는 수의 성질에 따라 전략을 나누는 그리디 접근이다.수들을 다음 네 종류로 분리한다.1보다 큰 양수→ 두 개씩 묶어서 곱하는 것이 이득음수→ 두 개씩 묶어서 곱하면 양수가 되어 이득1→ 어떤 수와 곱해도 이득이 없으므로 그냥 더함0→ 남는 음수 하나를 제거(상쇄)하는 용도로 사용이를 위해양수(>1)는 내림차순 우선순위 큐음수는 오름차순 우선순위 큐로 관리한다.구현 시 주의할 점1은 절대 곱하지 않는다.1 × x ≤ 1 + x 이므로 항상 더하는 게 이득이다.음수가 하나 남았을..