🔗 문제 링크https://www.acmicpc.net/problem/2748📌 문제 개요피보나치 수열에서 N번째 값을 구하는 문제이다.피보나치 수열은 다음과 같은 규칙을 가진다.F(0) = 0F(1) = 1F(n) = F(n-1) + F(n-2)N의 범위가 최대 90이므로 일반적인 재귀 방식은 비효율적📌 접근 방법피보나치 수는 이전 두 값을 이용해 계산할 수 있으므로배열 대신 두 개의 변수만 사용해서 해결할 수 있다. 또한 반복문을 사용하면 시간복잡도를 O(N)으로 줄일 수 있다.📌 핵심 아이디어피보나치는 이전 값 2개만 알면 계산 가능매 반복마다 값 이동이 중요하다temp = one + twoone = twotwo = temp N ≤ 90 이므로 long 타입 사용 가능📌 전체 코드impor..

🔗 문제 링크https://www.acmicpc.net/problem/9237📌 문제 개요나무를 하루에 하나씩 심을 수 있고,각 나무는 자라는 데 시간이 다르게 걸린다. 모든 나무가 다 자란 다음 날 이장님을 초대해야 할 때,가장 빠른 초대 날짜를 구하는 문제📌 접근 방법이 문제의 핵심은 심는 순서오래 걸리는 나무를 뒤에 심으면 전체 시간이 늦어짐따라서 오래 걸리는 나무부터 먼저 심는 것이 최적 즉, 내림차순 정렬 후 순서대로 심기📌 핵심 아이디어i번째 나무는 (i + 1)일에 심는다해당 나무 완료일:tree[i] + (i + 1) 전체 완료일은 최댓값초대는 다음 날이므로 +1📌 전체 코드import java.io.BufferedReader;import java.io.IOException;imp..

🔗 문제 링크https://www.acmicpc.net/problem/16395 📌 문제 개요파스칼의 삼각형에서 N번째 줄의 K번째 값을 구하는 문제이다.각 값은 바로 위의 두 값의 합으로 구성되는 특징을 가진다. 📌 접근 방법이 문제는 DP 방식으로 직접 삼각형을 구성하거나조합 공식으로도 해결할 수 있다. 직관적인 이해를 위해 2차원 배열을 이용한 DP 방식으로 풀이 📌 핵심 아이디어양 끝 값은 항상 1내부 값은 위 두 값의 합점화식arr[i][j] = arr[i-1][j-1] + arr[i-1][j] 또한 이 문제는 (N-1)C(K-1)과 동일하다 📌 전체 코드import java.io.BufferedReader;import java.io.IOException;import java.io.In..

🔗 문제 링크https://www.acmicpc.net/problem/2628📌 문제 개요가로 M, 세로 N 크기의 종이를 여러 번 자른다.각 자르기는 가로(0) 또는 세로(1) 방향으로 이루어진다. 모든 자르기가 끝난 후가장 큰 직사각형 조각의 넓이를 구하는 문제이다.📌 접근 방법가로로 자르면 → 세로 길이가 나뉨세로로 자르면 → 가로 길이가 나뉨따라서가로선 리스트 (세로 분할)세로선 리스트 (가로 분할)이렇게 2개로 분리해서 관리한다.그리고시작점(0)끝점(전체 길이)을 반드시 포함해야 한다.📌 핵심 아이디어자른 위치들을 정렬인접한 값끼리 차이를 구하면 조각 길이 생성예 : 0, 2, 3, 8 → 길이: 2, 1, 5 가장 큰 길이만 필요 최종 결과 : 최대 가로 길이 × 최대 세로 길이 📌 ..

🔗 문제 링크https://www.acmicpc.net/problem/13301📌 문제 개요정사각형 타일을 이어 붙여 도형을 만들 때,타일의 변 길이가 특정 규칙(피보나치 형태)을 따른다.이때 N번째 도형의 둘레 길이를 구하는 문제이다.📌 접근 방법타일의 변 길이는 피보나치 수열도형의 가로, 세로는 연속된 피보나치 값으로 구성됨최종적으로 직사각형 형태가 되므로둘레 = 2 × (가로 + 세로)📌 핵심 아이디어피보나치 수열을 이용해 변 길이를 계산배열 없이 변수 2개로 최적화a = 이전 값b = 현재 값 반복하면서 갱신📌 전체 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;publi..

🔗 문제 링크https://www.acmicpc.net/problem/1769📌 문제 개요주어진 숫자 X에 대해 각 자리 숫자의 합을 반복하여 한 자리 수가 될 때까지 진행이 과정의 횟수를 출력하고, 최종 결과가 3의 배수인지 판별하는 문제📌 접근 방법숫자의 자릿수가 매우 크기 때문에 String으로 입력받는다각 자리 숫자를 더하는 과정을 반복한다한 자리 수가 될 때까지 while문을 사용한다반복 횟수를 카운트한다📌 핵심 아이디어각 자리수의 합을 반복하면 결국 한 자리 수가 된다 (디지털 루트 개념)최종 값이 3으로 나누어 떨어지면 3의 배수문자열을 이용하여 자리수를 안전하게 처리하는 것이 중요📌 전체 코드import java.io.BufferedReader;import java.io.IOExc..

🔗 문제 링크🔗 https://www.acmicpc.net/problem/5800📌 문제 개요각 반의 학생 점수가 주어질 때, 반마다 다음 값을 구하는 문제이다.최대 점수 (Max)최소 점수 (Min)인접 점수 간 최대 차이 (Largest gap)📌 접근 방법이 문제는 정렬을 기반으로 해결점수를 배열에 저장오름차순 정렬 수행정렬된 배열을 기준으로첫 번째 값 → 최소값마지막 값 → 최대값인접한 점수 차이를 계산하며 최대 gap을 찾는다📌 핵심 아이디어이 문제의 핵심은 Largest gap의 정의단순히 최대값 - 최소값이 아니라정렬 후 인접한 점수 간 차이의 최대값 예시: 70 71 72 100정렬 후: 70 71 72 100gap:71 - 70 = 172 - 71 = 1100 - 72 = 28L..

🔗 문제 링크https://www.acmicpc.net/problem/2828📌 문제 개요사과가 떨어지는 위치가 순서대로 주어질 때,크기 M의 바구니를 좌우로 이동시켜 모든 사과를 받는다.이때 바구니 이동 거리의 최솟값을 구하는 문제📌 접근 방법바구니를 [left, right] 범위로 관리사과 위치가 바구니 안이면 이동하지 않음바구니 밖이면 최소 거리만큼 이동📌 핵심 아이디어바구니는 항상 길이 M 유지이동은 항상 최소 거리상황은 3가지바구니 안 → 이동 X왼쪽 밖 → 왼쪽 이동오른쪽 밖 → 오른쪽 이동📌 전체 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class ..

🔗 문제 링크🔗 https://www.acmicpc.net/problem/16435📌 문제 개요스네이크버드는 자신의 길이보다 작거나 같은 높이의 과일만 먹을 수 있다.과일을 먹을 때마다 길이는 1씩 증가한다.주어진 과일들을 적절히 먹어 최대 길이를 구하는 문제📌 접근 방법과일을 아무 순서로 먹는 것이 아니라 작은 것부터 먹는 것이 핵심큰 과일부터 먹으면 이후 작은 과일을 못 먹는 경우 발생따라서: 오름차순 정렬 후 순차 탐색📌 핵심 아이디어현재 길이 >= 과일 높이 → 먹기 (길이 +1)현재 길이 한 번 막히면 뒤는 전부 불가능📌 전체 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamRead..

🔗 문제 링크https://www.acmicpc.net/problem/1652📌 문제 개요NxN 크기의 방이 주어지고, .은 빈칸, X는 벽을 의미한다.가로 또는 세로로 연속된 빈칸이 2칸 이상이면 누울 수 있는 자리로 판단- 가로 / 세로 각각 가능한 자리 개수를 구하는 문제📌 접근 방법이 문제는 단순 구현 문제로연속된 '.'의 길이를 세는 방식으로 해결할 수 있다.가로 방향 탐색한 행씩 보면서 '.' 개수 카운트'X'를 만나면 구간 종료세로 방향 탐색동일한 방식으로 열 기준 탐색📌 핵심 아이디어연속된 '.' 구간을 찾는다구간 길이가 2 이상이면 카운트'X'를 기준으로 구간을 나눈다가로와 세로는 완전히 별개로 계산📌 전체 코드import java.io.BufferedReader;import j..