🔗 문제 링크 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 📖 풀이 과정 - 다이나믹 프로그래밍 유형 + 재귀 유형의 문제입니다. - 문제의 조건을 종합해보면, 현재 인덱스의 최소값은 바로 직전 색깔을 제외한 다른 두가지 색깔중에서 최소값을 더한 값입니다. - 그렇기에 어떠한 한 색깔의 특정 인덱스에서의 값은 이전 색깔을 제외한 두가지 색깔중에 최소값을 구해야 합니다. - 이러한 방식으로 답을 찾아나가면, 답이 될 수 있는 값은 빨강색, 초록색, 파란색 3가지입니다. - 따라서, 이 ..
🔗 문제 링크 15657번: N과 M (8) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 📖 풀이 과정 - 재귀 유형의 문제입니다. - 비내림차순으로 출력을 하는 것이 조건문을 설정하는데 중요한 부분입니다. - 매개변수가 0일때는 일단 넣어야 하기에, answer 배열 변수에 값을 할당합니다. - 그 외의 값을 할당할 때는 모든 경우의 수에서 비내림차순인지만 확인하여 값을 할당하는식으로 구현했습니다. 💻 코드 import java.io.BufferedReader; import java.io.IOException; import j..
🔗 문제 링크 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 📖 풀이 과정 - 재귀 유형의 문제입니다. - 순차적으로 출력을 해야하기 때문에 재귀 메소드 호출 이전에 정렬을 해야 합니다. - 재귀 메소드에서는 같은 값 외에 배열의 모든 값들과 짝이 지어져야 합니다. - 따라서, 기존의 boolean 타입의 visited 배열을 사용하지 않고 재귀적으로 메소드를 호출하여 결과를 출력합니다. 💻 코드 import java.io.BufferedReader; import java.io.IOException;..
🔗 문제 링크 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 📖 풀이 과정 - 재귀 유형의 문제입니다. - 15650번 문제의 조건문에서 이전의 값(마지막에 배열에 할당한 값)과 지금 넣을 값이 같을 경우를 고려해야 합니다. - 저는 단순히 이 두가지에 대한 조건문을 명시해서 구현했습니다. - 추후, 좀 더 간단하게 작성을 해보겠습니다. 💻 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader..
🔗 문제 링크 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 📖 풀이 과정 - 누적합 유형의 문제입니다. - 누적합 알고리즘에 대한 이해가 필요합니다. - 만약, 단순 for 반복문으로 해결하려한다면, 시간초과가 발생할 것입니다. - 값을 입력받을 때부터 배열에 누적된 합을 할당합니다. - 출력을 할 때는 (기준 인덱스) 까지의 배열값에서 (시작값 - 1) 인덱스를 이용하여 배열값을 반환합니다. 💻 코드 import java.io.BufferedReader; import java.io...
🔗 문제 링크 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 📖 풀이 과정 - 다이나믹 프로그래밍 유형의 문제입니다. - 자연수 n을 최소 개수의 제곱수 합의 개수로 표현하면 다음과 같습니다. - 1 -> 1 - 2 -> 2 - 3 -> 3 - 4 -> 1 - 5 -> 2 - 6 -> 3 - 7 -> 4 - 8 -> 1 - 9 -> 1 - 10 -> 2 - 11 -> 3 - 12 -> 4 - 13 -> 5 - 14 -> 6 - 15 -> 7 - 16 -> 1 - 이를 통해 ..
