이 문제는 주어진 계단을 오를 때 얻을 수 있는 최대 점수를 구하는 문제입니다. 계단은 특정 규칙에 따라 올라야 하며, 동적 계획법(Dynamic Programming)을 사용하여 해결할 수 있습니다. 문제를 분석하고 접근 방법을 정리한 후, 최종적인 정답 코드를 확인해 보겠습니다. 1. 문제 설명백준 2579번 문제 “계단 오르기”는 주어진 계단을 오르면서 얻을 수 있는 최대 점수를 구하는 문제입니다. 계단을 오를 때 다음 규칙을 따라야 합니다: 1) 계단은 한 번에 한 계단 또는 두 계단씩 오를 수 있습니다. 2) 연속된 세 개의 계단을 모두 밟아서는 안 됩니다. 3) 마지막 계단은 반드시 밟아야 합니다. 2. 문제 접근법이 문제를 해결하기 위해 동적 계획법을 사용합니다. 핵심 아이디어는 각 계단에..
코딩테스트
이번 글에서는 백준 1753번 문제인 “최단경로” 문제를 함께 해결해 보겠습니다. 이 문제는 그래프에서 특정 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 찾는 문제로, 다익스트라 알고리즘을 사용하여 해결할 수 있습니다. 문제를 분석하고, 접근 방법을 정리한 후, 최종적인 정답 코드를 확인해 보겠습니다. 문제 URL: https://www.acmicpc.net/problem/1753 1. 문제 설명 1) 문제 개요주어진 그래프에서 특정 시작 정점에서 다른 모든 정점으로의 최단 경로를 찾는 문제입니다. 그래프는 방향성과 가중치를 가진 간선들로 이루어져 있으며, 시작 정점으로부터 각 정점까지의 최단 거리를 계산해야 합니다. 2) 입력 • 첫 번째 줄: 정점의 수 V (1 ≤ V ≤ 20,000)와 간선..
이번 글에서는 백준 14889번 문제 “스타트와 링크”를 함께 해결해 보겠습니다. 이 문제는 N명의 사람들이 두 팀으로 나누어질 때, 두 팀의 능력치 차이를 최소화하는 문제입니다. 1. 문제 설명1) 문제 개요 • N명의 사람들이 두 팀으로 나뉘어 게임을 합니다. • 각 사람마다 다른 사람과 팀을 이루었을 때의 능력치가 주어집니다. • 두 팀의 능력치 차이를 최소화하는 것이 목표입니다. 2) 입력 • 첫 번째 줄에 사람의 수 N이 주어집니다. (4 ≤ N ≤ 20, N은 짝수) • 두 번째 줄부터 N개의 줄에 걸쳐 각 사람의 능력치가 주어집니다. 3) 출력 • 두 팀의 능력치 차이의 최솟값을 출력합니다. 2. 접근법1) 입력받기 • sys.stdin.readline을 사용하여 입력 속도를 높입니다. • ..
안녕하세요! 오늘은 백준의 1946번 문제인 “신입 사원” 문제를 함께 풀어보겠습니다. 이 문제는 여러 명의 지원자 중에서 서류 심사와 면접 순위를 기반으로 신입 사원을 선발하는 문제입니다. 함께 문제를 해결해보도록 하죠! 1. 문제 설명 1) 여러 명의 지원자가 있습니다. 각 지원자는 서류 심사 순위와 면접 순위가 매겨져 있습니다. 2) 두 순위 중 하나라도 다른 지원자보다 높으면 그 지원자는 선발될 수 없습니다. 3) 이러한 조건 하에서 최대한 많은 신입 사원을 선발하려 합니다. 문제 URL: https://www.acmicpc.net/problem/1946 2. 접근법 1) 입력받기: 테스트 케이스 수와 각 테스트 케이스별 지원자의 서류 및 면접 순위 정보를 입력받습니다. 2) 정렬: 서류 심사 순..
안녕하세요! 오늘은 백준 온라인 저지의 2503번 문제, “숫자 야구”에 대해 살펴보겠습니다. 이 문제는 주어진 조건에 맞춰 가능한 세 자리 숫자를 맞추는 문제입니다. 문제를 해결하는 과정과 함께 Python으로 작성한 정답 코드를 소개하겠습니다. 1. 문제 설명숫자 야구는 상대방이 생각하고 있는 세 자리 숫자를 질문을 통해 맞추는 게임입니다. 각 질문에 대해 스트라이크(Strikes)와 볼(Balls)의 개수를 받게 됩니다. 스트라이크는 숫자와 위치가 모두 맞는 경우, 볼은 숫자만 맞는 경우를 의미합니다. 우리의 목표는 주어진 질문과 답변을 바탕으로 가능한 숫자의 개수를 구하는 것입니다. 주어진 식은 다음과 같습니다: • 스트라이크: 숫자와 위치가 모두 맞는 경우 • 볼: 숫자는 맞지만 위치가 다른 ..
