연습장/백준(BOJ) 문제풀이

[백준 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..

[백준 1389] 케빈 베이컨의 6단계 법칙 with Node.js

문제 링크 https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 풀이 const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); const [ N, M ] = input.shift().split(' ').map(v => +v); const bacon = new Array(N+1).fill(0); const g..

[백준 9375] 패션왕 신해빈 with Node.js

문제 링크 https://www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 풀이 const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); const iterator = input[Symbol.iterator](); let T = +iterator.next().value; w..

[백준 5525] IOIOI with Python

문제 링크 https://www.acmicpc.net/problem/5525 5525번: IOIOI N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 www.acmicpc.net 풀이 N = int(input()) M = int(input()) S = input() P = 'IO' * N + 'I' switch = False count = 1 output = 0 for i in range(M): if not switch and S[i] == 'I': switch = True elif switch..

[백준 17626] Four Squares with Node.js

문제 링크 https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 풀이 const solve = n => { const dp = new Array(n+1).fill(0); dp[1] = 1; for (let i=2; i