연습장

[백준 10972] 다음 순열 with Node.js

문제 링크 https://www.acmicpc.net/problem/10972 10972번: 다음 순열 첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net 풀이 const [ N, ...arr ] = require('fs').readFileSync('/dev/stdin').toString().trim().split(/\s+/).map(v => +v); const solve = (N, arr) => { const arrCopy = [...arr].sort((a, b) => b - a); if (arr.every((v, i) => v === arrCopy[i])) { console.log(-1); } ..

[백준 2294] 동전 2 with Python

문제 링크 https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 풀이 import sys n, k = map(int, sys.stdin.readline().split()) coin = [int(sys.stdin.readline()) for _ in range(n)] dp = [10001 for _ in range(k+1)] dp[0] = 0 for i in range(1, k+1): for j in coin: if i ..

[백준 15663] N과 M (9) with Node.js

문제 링크 https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 풀이 const solve = (N, M, arr) => { const chosen = new Array(N).fill(false); const permutation = []; const output = []; const recursion = () => { if (permutation.length === M) { output.push(permutation.join(' ')); } el..

[백준 2293] 동전 1 with Python

문제 링크 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 import sys n, k = map(int, sys.stdin.readline().split()) coin = [int(sys.stdin.readline()) for _ in range(n)] dp = [1]+[0]*k for value in coin: for i in range(1, k+1): if i < value: continue dp[i] += dp[i-value] pri..

[백준 11057] 오르막 수 with Python

문제 링크 https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 풀이 N = int(input()) dp = [[0]*10 for _ in range(N+1)] dp[1] = [1]*10 for i in range(2, N+1): for j in range(10): dp[i][j] += sum([dp[i-1][k] for k in range(j+1)]) print(sum(dp[N])%10007) dp[N]은 N자리..

[백준 9251] LCS with Python

문제 링크 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀이 X = input() Y = input() LCS = [[0]*(len(Y)+1) for _ in range(len(X)+1)] for i in range(1, len(X)+1): for j in range(1, len(Y)+1): if X[i-1] == Y[j-1]: LCS[i][j] = LCS[i-1][j-1] + 1 else: LC..

[백준 10844] 쉬운 계단 수 with Python

문제 링크 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 N = int(input()) dp = [[0]*10 for _ in range(N+1)] dp[1] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1] for i in range(2, N+1): for j in range(10): if j == 0: dp[i][0] = dp[i-1][1] elif j == 9: dp[i][9] = dp[i-1][8] else: dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] print(sum(dp[N])%1000000000) 길이가..

[백준 16928] 뱀과 사다리 게임 with Node.js

문제 링크 https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x { input.shift(); const temp = [...new Array(101)].map((_, i) => i); for (const i of input) { const [ start, end ] = i.split(' ').map(v => +v); temp[start] = end; }..

[백준 15657] N과 M (8) with Node.js

문제 링크 https://www.acmicpc.net/problem/15657 15657번: N과 M (8) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 풀이 const solve = (N, M, arr) => { const permutation = []; const output = []; const recursion = () => { if (permutation.length === M) { output.push(permutation.join(' ')); } else { for (const i of arr) { if (permu..

[백준 11286] 절댓값 힙 with Python

문제 링크 https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 풀이 import sys class Heap: def __init__(self, L=[]): self.arr = L def compare(self, a, b): if abs(self.arr[a]) > abs(self.arr[b]): return True elif abs(self.arr[a]) < abs(self.arr[b]): return False else: re..