[BOJ][DP] 1351. 무한 수열 (java)

✏️ 문제 https://www.acmicpc.net/problem/1351문제무한 수열 A는 다음과 같다.A0 = 1Ai = A⌊i/P⌋ + A⌊i/Q⌋ (i ≥ 1)N, P와 Q가 주어질 때, AN을 구하는 프로그램을 작성하시오.입력첫째 줄에 3개의 정수 N, P, Q가 주어진다.출력첫째 줄에 AN을 출력한다. 🔢 알고리즘 #DP  🤯 풀이 방법 처음 제출한 코드는 ⬇️수열이라고 1부터 하나씩 계산하며 올라가면 메모리 초과가 난다. import java.util.*;import java.io.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new ..

• format_list_bulleted BOJ
• · 2025. 2. 21.
• textsms

[BOJ][DP] 9251. LCS (java)

✏️ 문제문제LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.입력첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.출력첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다. 🔢 알고리즘 #DP  #LCS  🤯 풀이 방법 [알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common SubsequenceLCS는 주로 최장 공통 부분수열(Longest Common Subse..

• format_list_bulleted BOJ
• · 2025. 2. 19.
• textsms

[BOJ][DP] 1003. 피보나치 함수 (java / python)

✏️ 문제  🔢 알고리즘 #DP  #다이나믹프로그래밍  🤯 풀이 방법 문제에서 재귀 함수, 출력 어쩌고 했다고 그대로 풀면 당연히 시간 초과가 난다.0부터 테스트케이스를 보면,0의 경우: 0 출력 후 리턴 1의 경우: 1 출력 후 리턴 2의 경우: call f(0), f(0) 이므로 f(0)의 출력 수와 f(1)의 출력 수를 더하면 3의 경우: call f(1), f(2) -> (0, 1) + (1, 1) = 4의 경우: call f(2), f(3) -> (1, 1) + (1, 2) = 5의 경우: call f(3), f(4) -> (1, 2) + (2, 3) = 6의 경우: call f(4), f(5) -> (2, 3) + (3, 5) =  숫자의 나열이 익숙하다. 1, 1, 2, 3, 5, 8, ..

• format_list_bulleted BOJ
• · 2025. 2. 17.
• textsms

[BOJ][우선순위큐] 11286. 절댓값 힙 (java)

✏️ 문제문제절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.배열에 정수 x (x ≠ 0)를 넣는다.배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.프로그램은 처음에 비어있는 배열에서 시작하게 된다.입력첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 정수는 -231보다 크고, 231보다 작다.출력입력에서 0이 주어진 회수만큼 ..

• format_list_bulleted BOJ
• · 2025. 2. 14.
• textsms

[BOJ][Greedy] 11399. ATM (java/python)

✏️ 문제문제인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다.사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1+4 = 8분이 필요하게..

• format_list_bulleted BOJ
• · 2025. 2. 11.
• textsms

[BOJ] 26043. 식당 메뉴 (java)

✏️ 문제문제여러 명의 학생이 식사하기 위하여 학교 식당을 향해 달려가고 있다. 학교 식당에 도착한 학생은 식당 입구에 줄을 서서 대기한다. 학교 식당에 먼저 도착한 학생이 나중에 도착한 학생보다 식당 입구의 앞쪽에서 대기한다. 식사는 1인분씩 준비된다. 식사 1인분이 준비되면 식당 입구의 맨 앞에서 대기 중인 학생 1명이 식당으로 들어가서 식사를 시작한다. 식사를 시작한 학생은 항상 식사를 마친다.학교 식당에서는 두 가지 메뉴가 제공되고 각각의 학생은 두 가지 메뉴 중에서 본인이 좋아하는 메뉴를 결정한 상태다. 학생이 학교 식당에 도착하고 식사가 준비되는 n개의 정보가 저장된 S가 주어진다. S에 저장된 첫 번째 정보부터 n번째 정보까지 순서대로 처리한 경우, 본인이 좋아하는 메뉴를 먹은 학생 목록 A..

• format_list_bulleted BOJ
• · 2025. 2. 7.
• textsms