Problem Solving
[백준] 10844번 쉬운 계단 수(feat. 다이나믹 프로그래밍)
[백준] 10844번 쉬운 계단 수(feat. 다이나믹 프로그래밍)
2023.02.01https://www.acmicpc.net/problem/10844 문제 접근 첫 번째 단계 (문제 요약 및 조건 파악) 인접한 모든 자리의 차이가 1인 수를 계단 수라고 한다, (0으로 시작하는 수는 계단수가 아니다) N이 주어지면, 길이가 N인 계단 수가 총 몇개 있는지 구해야 한다. N은 1
[백준] 1789번 수들의 합(feat. 그리디, 수학)
[백준] 1789번 수들의 합(feat. 그리디, 수학)
2023.01.26https://www.acmicpc.net/problem/1789 문제 분석 첫 번째 단계(문제 요약 및 조건 파악) 서로 다른 N개의 자연수의 합을 S라고 한다. S가 주어졌을 때, N의 최댓값은 얼마인지 구해야 한다. 입력으로는 자연수 S(1
[백준] 1463번 계단 오르기(feat. 다이나믹 프로그래밍, BFS)
[백준] 1463번 계단 오르기(feat. 다이나믹 프로그래밍, BFS)
2023.01.26https://www.acmicpc.net/problem/1463 문제 분석 첫 번째 단계 (문제 요약 및 조건 파악하기) 정수 X에 사용할 수 있는 연산은 3가지다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위의 세 연산을 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 구해서 출력해야 한다. 입력을 보면, N의 범위는 1
[백준] 1912번 연속합(feat. 다이나믹 프로그래밍)
[백준] 1912번 연속합(feat. 다이나믹 프로그래밍)
2023.01.25https://www.acmicpc.net/problem/1912 문제 분석 첫 번째 단계 (문제 요약 및 조건 파악하기) n개의 정수로 이루어진 임의의 수열이 주어진다. 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하는 것이다. ex) 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어지면, 여기서 정답은 12 + 21 인 33이 정답이 된다. 첫째 줄에는 정수 n이 주어진다. (1
[백준] 2579번 계단 오르기(feat. 다이나믹 프로그래밍)
[백준] 2579번 계단 오르기(feat. 다이나믹 프로그래밍)
2023.01.24https://www.acmicpc.net/problem/2579 문제 분석 첫 번째 단계 (문제 요약 및 조건 파악하기) 시작점에서 출발하여 마지막 도착 계단까지 가는 경로 중에, 가중치가 가장 큰 경로를 찾아서 해당 가중치를 반환해야 하는 문제이다. 규칙으로는 한 번에 한 계단 또는 두 계단 씩 오를 수 있고, 연속된 세 개의 계단을 모두 밟을 수는 없다.(시작점은 포함 X) 마지막 도착 계단은 무조건 밟아야 한다. 입력으로 주어지는 계단의 개수는 300이하의 자연수, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다. 두 번째 단계 (문제의 핵심 파악하기) 우리는 어찌되었건, n번째 계단에 올라야 한다. 그렇다면, n번째 계단에 오르는 경우의 수를 생각해보자. 총 4가지로 생각할 수 있다. 1...
[백준] 9370번 미확인 도착지(feat. 다익스트라)
[백준] 9370번 미확인 도착지(feat. 다익스트라)
2023.01.21https://www.acmicpc.net/problem/9370 문제 분석 첫 번째 단계(문제 요약 및 조건 파악하기) 처음에, 이 문제를 읽고, 한번에 머리에 안들어와서 당황했다. 입력도 은근히 많았고 말이다. 호흡을 가다듬고, 다시한번 집중해서 읽으면서 중요한 부분을 요약했다. 이해하고나니, 별거 아니었다. 정리하자면, s 지점에서 출발하고, 목적지 후보들이 있고, 목적지에는 최단 거리로 가야한다. 경로와 관련된 조건이 있는데, g와 h 교차로 사이에 있는 도로를 무조건 지나가는 경로여야 한다. 목적지 후보들 중, 목적지로 불가능한 경우를 제외하고, 다른 목적지들을 공백으로 분리시켜 오름차순의 정수로 출력해야 하는 문제다. 입력을 풀어서 정리하면 아래와 같다. 테스트케이스 개수 n(교차로), m(도..