문제 링크:https://www.acmicpc.net/problem/9655 📝 문제 요약두 명의 플레이어가 번갈아가며 돌을 가져가는 게임입니다.돌은 한 번에 1개 또는 3개씩 가져갈 수 있으며, 마지막 돌을 가져가는 사람이 승리합니다.상근이가 먼저 시작하며, 두 플레이어는 항상 최적의 전략으로 게임을 진행합니다.입력으로 주어진 돌의 개수 N(1 ≤ N ≤ 1000)에 따라 승자를 구합니다.📌 접근법1, 게임의 성질 파악:현재 돌의 개수 i에서 돌을 가져가면 남은 돌의 개수는 i - 1 또는 i - 3입니다.상대가 남은 돌의 개수로 패배하는 경우라면 현재 플레이어가 승리합니다.2, DP (동적 계획법) 사용:dp[i]: 돌이 i개 남았을 때 이기는 사람을 나타냄.true: 상근이(SK)가 이김.fal..

문제 링크 : https://www.acmicpc.net/problem/2116 문제 요약이 문제는 여러 개의 주사위를 쌓아 옆면 숫자의 합이 최대가 되도록 하는 문제입니다. 주사위를 쌓을 때 다음 규칙을 지켜야 합니다:각 주사위의 아래면 숫자는 바로 아래 주사위의 윗면 숫자와 같아야 합니다.주사위는 회전할 수 있지만, 위아래 위치는 고정됩니다.옆면의 숫자 중 가장 큰 값을 선택하여 합을 계산합니다.문제는 옆면 숫자의 합의 최대값을 구하는 것입니다.문제 해결 접근법1. 주사위의 위/아래 면 설정주사위의 각 면은 A,B,C,D,E,FA, B, C, D, E, FA,B,C,D,E,F로 표현됩니다.아래 면과 윗면의 관계는 다음과 같습니다:A(0)↔F(5)B(1)↔D(3)C(2)↔E(4)아래 면의 값을 기준으로..

문제 링크 :https://www.acmicpc.net/problem/1374문제 요약이 문제는 N개의 강의를 최소한의 강의실 개수로 배정하는 것이 목표입니다. 강의실은 동시에 두 개 이상의 강의를 진행할 수 없지만, 한 강의의 종료 시간과 다른 강의의 시작 시간이 겹치는 것은 허용됩니다.조건:각 강의는 시작 시간과 종료 시간을 가집니다.한 강의실에서 동시에 두 개 이상의 강의를 진행할 수 없습니다.주어진 강의 정보를 기반으로 필요한 최소 강의실 개수를 구해야 합니다.접근법이 문제는 그리디 알고리즘과 우선순위 큐를 사용하여 효율적으로 해결할 수 있습니다. 접근 과정은 다음과 같습니다: 1, 강의 정렬:강의는 시작 시간을 기준으로 정렬합니다. 시작 시간 기준으로 정렬하면, 강의 배정을 순차적으로 진행할 수..

문제 링크 : https://www.acmicpc.net/problem/2212 문제 요약한국도로공사는 고속도로에 설치된 N개의 센서가 수집한 데이터를 분석하기 위해 K개의 집중국을 세우려고 합니다. 각 집중국은 일정 구간을 커버할 수 있으며, 모든 센서가 최소 하나의 집중국과 통신할 수 있어야 합니다. 집중국의 수신 영역 길이의 합을 최소화하는 것이 목표입니다.이 문제는 센서들이 특정 위치에 고정되어 있고 집중국의 수신 구간 길이를 최소화하면서 모든 센서들을 커버해야 하는 상황을 다룹니다.접근법1, 센서 위치 정렬: 센서 위치를 오름차순으로 정렬하면 인접한 센서 간의 거리를 쉽게 계산할 수 있습니다.2, 센서 간 거리 계산: 정렬된 센서 간의 거리를 계산하여 각 인접한 센서들 사이의 거리를 구해 리스트..

문제 링크 : https://www.acmicpc.net/problem/31926문제 요약목표: daldidalgo라는 문자열을 총 N번 반복 입력한 후 마지막에 daldidan으로 끝내는 문자열을 최소 시간 내에 완성해야 한다.제약:문자 하나씩 입력하거나, 이미 입력한 문자열을 복사해 붙여넣는 두 가지 작업만 가능.시간 복잡도 효율화를 위해 복사-붙여넣기를 활용하여 빠르게 반복 횟수를 채워야 한다.문제 해결 아이디어1, 첫 번째 문자열 입력:"daldidalgo"를 처음 입력하는 데 8초가 걸린다고 가정.이 입력 후 복사-붙여넣기 작업을 통해 최대한 빠르게 문자열을 확장해 나가는 방식으로 최적화 가능.2, 복사-붙여넣기 최적화:복사-붙여넣기 작업으로 현재까지 입력된 daldidalgo의 수를 2배로 늘..

문제 링크 : https://www.acmicpc.net/problem/2847 문제 설명동준이가 만든 게임에는 여러 레벨이 있고, 각 레벨을 클리어할 때 점수를 얻는다. 이 점수는 레벨이 높아질수록 커져야 하지만, 현재는 쉬운 레벨의 점수가 어려운 레벨보다 높은 경우가 존재한다. 이를 해결하기 위해 각 레벨의 점수를 감소시켜야 하며, 이때 최소한의 감소 횟수로 점수를 조정하는 것이 목표다.접근법이 문제는 그리디 알고리즘을 사용하여 해결할 수 있다. 가장 높은 레벨부터 점검하며, 현재 레벨 점수가 이전 레벨보다 낮거나 같을 경우 이전 레벨의 점수를 현재 레벨보다 1 낮게 만든다. 이 과정을 반복하면서 각 레벨의 점수를 점진적으로 감소시키며, 필요할 때마다 감소 횟수를 누적하여 최종 답을 도출한다.#inc..

문제 링크 : https://www.acmicpc.net/problem/13417문제 설명태욱이는 일렬로 놓인 N장의 카드에서 차례대로 카드를 가져와서 왼쪽 또는 오른쪽에 배치해 가장 사전 순으로 빠른 문자열을 만들고자 한다. 각 테스트 케이스마다 초기 카드 순서가 주어지며, 목표는 이 카드들로 만들 수 있는 가장 작은 사전 순 문자열을 출력하는 것이다.접근법처음에는 그리디 알고리즘이 필요하다는 점을 명확히 인식하지 못했으나, 문제를 분석하면서 각 단계에서 최적의 선택을 해야 한다는 점을 깨달았다. 이를 통해 매 순간 왼쪽 또는 오른쪽에 카드를 배치하여 사전 순으로 가장 빠른 선택을 반복하는 것이 필요하다는 결론에 도달했다.비교: 현재 카드를 이미 배치한 문자열의 첫 번째 문자와 비교한다.배치: 사전 순..

문제 링크 : https://www.acmicpc.net/problem/14916문제 설명춘향이는 2원과 5원짜리 동전만으로 손님에게 최소 개수의 동전으로 거스름돈 NNN원을 주어야 한다. 2원과 5원짜리 동전이 무한정 있을 때, 정확히 NNN원을 거슬러 줄 수 있는 최소 동전 개수를 구하는 문제이다.접근법처음에는 이 문제에 그리디 알고리즘이 필요하다는 점을 인지하지 못했지만, 문제를 분석하면서 각 단계에서 최적의 선택을 해야 함을 깨달았다.그리디 알고리즘을 적용하기 위한 조건은 다음과 같다: 1, 큰 단위의 동전 우선 사용: 5원짜리 동전이 2원짜리보다 크기 때문에, 큰 단위인 5원짜리를 우선적으로 사용해 거슬러 줌으로써 동전 개수를 최소화할 수 있다. 2, 남은 금액에 맞는 조정: 5원으로 나누어떨어..