https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 🤔 해결방법 1. dp 배열 초기화하기 (각 요소 = i번째 계단에 오를 때까지 얻을 수 있는 최대값) 2. dp[1] = arr[1], dp[2] = arr[1] + arr[2] 로 설정하기 3. 3번째 칸부터는 dp[i - 3] + arr[i - 1] + arr[i]와 dp[i - 2] + arr[i] 이렇게 두 경우 중 최대값 넣어주기 🔑 풀이 const input = require("fs") // .r..
https://www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 🤔 해결방법 1. dp 배열 초기화 2. 0번째, 1번째 수 0, 1로 지정 3. i번째 = i-2번째 + i-1번째라는 규칙으로 for문 작성 이 때, BigInt 사용 4. 마지막 출력에서 toString사용 🔑 풀이 const input = require("fs") // .readFileSync("/dev/stdin") .readFileSync(__dirn..
[백준] 꿀 아르바이트, 블로그, DNA 비밀번호 (javascript)
https://www.acmicpc.net/problem/12847 12847번: 꿀 아르바이트 월세를 내기 바로 전 날 까지 인 n (1 ≤ n ≤ 100,000) 일과 일을 할 수 있는 날 m (0 ≤ m ≤ n) 일이 주어진다. 그 다음 줄 에는 1일부터 n일 까지 일급 Ti가 순서대로 주어진다. (0 < Ti ≤ 1,000,000) www.acmicpc.net 🤔 해결방법 1. 초기값 = 처음부터 m개의 합 2. 슬라이딩 윈도우로 앞에 하나 빼고 뒤에 하나 더하기 3. 그 값을 profit에 push 4. 2,3번 반복 5. profit에서 가장 큰 값 출력 🔑 풀이 const input = require("fs") // .readFileSync("/dev/stdin") .readFileSync(..
https://www.acmicpc.net/problem/3226 3226번: 전화 요금 첫째 줄에 상근이가 건 전화의 수 N이 주어진다. (1 ≤ N ≤ 100) 다음 N개 줄에는 상근이가 건 전화에 대한 정보가 HH:MM DD와 같은 형식으로 주어진다. HH:MM은 전화를 건 시간이며, DD는 통화 시간이 www.acmicpc.net 🤔 해결방법 1. 전화를 건 시간과 통화 시간 값을 이중 배열로 저장 2. 7:00부터 19:00까지에 해당되면 fee += 통화 시간 x 10원, 19:00부터 7:00까지에 해당되면 fee += 통화 시간 x 5원 3. 이때 18시에서 19시로 넘어가는 경우와 6시에서 7로 넘어가는 경우를 나눠서 계산 🔑 풀이 먼저 입력되는 전화를 건 시간과 통화 시간 값들을 이중 ..
https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 🤔 해결방법 1. dp 배열을 생성하고 0으로 초기화 2. 각 물건에 대해 가능한 모든 무게(j)에 대해 dp[j] 값을 갱신 (새로운 dp[j]는 기존의 dp[j]와 dp[j - 물건 무게] + 물건 가치 중 큰 값으로 갱신) 3. dp 배열의 k번째 요소 출력 🔑 풀이 처음에는 물건의 무게가 최대 무게와 같은 경우와 작은 경우로..
https://www.acmicpc.net/problem/11441 11441번: 합 구하기 첫째 줄에 수의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 둘째 줄에는 A1, A2, ..., AN이 주어진다. (-1,000 ≤ Ai ≤ 1,000) 셋째 줄에는 구간의 개수 M이 주어진다. (1 ≤ M ≤ 100,000) 넷째 줄부터 M개의 줄에는 www.acmicpc.net 🤔 해결방법 1. 0인 요소가 n+1개인 배열을 만들고 누적 합산 숫자를 해당 인덱스에 넣어준다 2. 끝지점 요소에서 시작요소-1 까지 뺀 값을 차례로 개행하여 출력한다 🔑 풀이 문제를 읽자마자 바로 구간의 합을 하나씩 더해주도록 풀었다. 역시나 호락호락하지 않은 백준은 시간초과를 뱉어냈다.😥 const input = requ..
https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 🤔 해결방법 1. 수열의 숫자를 만들기 위해 만들려는 숫자가 스택의 top에 올 때까지 필요한 숫자를 스택에 push 2. 만들려는 숫자가 top에 있으면 pop 3. 만들 수 없는 경우는 'NO'를 반환 🔑 풀이 처음 문제를 읽었을 땐 한 번에 이해가 잘 가지 않았다. 다음과 같이 예제 1번의 실행 순서를 적어보며..
[백준] 촌수계산 (javascript)
https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 🤔 해결방법 1. 필요한 변수들 할당하고 그래프 생성 2. 촌수를 계산할 a의 인접노드를 차례로 순회하며 해당 촌수가 0이면 a의 촌수 +1로 업데이트 후 재귀 3. 촌수를 계산받을 사람의 촌수를 출력, 이 때 0이라면 -1을 출력 🔑 풀이 일반적으로 노드를 이동할 때 조건이 붙으면 DFS, 최단거리를 구하거나 인접노드를 공통적으로 처리해야할 때는 BFS를 사용한다는 것을 알게..