흙금이네 블로그

아이디어 동적 계획법으로 각 상담이 끝나는 시점의 최대 수익을 갱신해 나간다. 풀이 #1 (Python) N+1 크기의 0으로 채워진 리스트 dp를 생성하는데, dp[i]에는 i일째의 최대 수익을 저장한다. for문에서 T와 P를 입력 받아 어제 수익 dp[i]가 오늘 수익 dp[i+1]보다 큰 경우 오늘 수익에 어제 수익을 저장한다. 이번 상담이 끝나는 T-1일 후가 퇴사 전이고, 상담으로 얻는 수익이 T-1일 후의 예정 수익보다 더 크면 값을 갱신한다. import sys input = sys.stdin.readline def solution(): N = int(input()) dp = [0]*(N+1) for i in range(N): T, P = map(int, input().split()) if..

아이디어 동적 계획법을 이용해 각 칸에서 이동할 수 있는 칸의 경우의 수를 증가시켜 나간다. 풀이 #1 (Python) 게임판의 수를 2차원 리스트 board에 저장하고, 이동 경로의 수를 저장하는 0으로 채워진 2차원 리스트 dp를 생성한다. board의 가장 오른쪽 아래 칸과 dp의 가장 왼쪽 위 칸에 각각 1을 저장한다. board의 가장 오른쪽 아래 칸 값을 1로 바꿔 해당 칸 dp에 해당 칸 경로의 수를 더하는 것을 막는다. 이중 for문에서 현재 칸 (i, j)에서 이동할 수 있는 칸 (i+board[i][j], j)와 (i, j+board[i][j])의 dp에 현재 칸 경로의 수를 더한다. import sys input = sys.stdin.readline def solution(): N =..

아이디어 S의 홀수 원소로 구분된 연속된 짝수 수열의 길이를 구한 후 그 길이의 합의 최댓값을 찾는다. 풀이 #1 (Python) 리스트 arr의 초기값으로 0을 넣어두고 S의 각 원소가 홀수면 arr에 0을 추가하고, 짝수면 arr의 마지막 값을 1 증가시킨다. 따라서 arr에는 짝수로 이루어진 수열의 길이가 홀수 원소로 구분되어 저장되고, 연속된 arr 원소들의 합은 그 원소 수만큼 S에서 홀수 원소를 삭제한 짝수로 이루어진 수열의 길이와 같다. arr을 복제해 리스트 dp에 저장하고, for문에서 앞의 홀수 원소를 반복 횟수만큼 삭제한 수열의 길이로 dp를 갱신해 나간다. 같은 for문 내에서 구한 값이 현재 결과에 영향을 미치지 않도록 dp의 원소들을 역순으로 갱신한다. def solution()..

아이디어 동적 계획법으로 피보나치 수를 구해 나간다. 풀이 #1 (Python) 피보나치 수를 저장하기 위해 0으로 채워진 N+1 크기의 리스트 dp를 생성하고, dp[1]의 값으로 1을 할당한다. for문에서 2부터 N까지의 수에 대해 앞의 두 피보나치 수의 합으로 피보나치 수를 계산하고, dp에 저장한다. N = int(input()) dp = [0]*(N+1) dp[1] = 1 for i in range(2, N+1): dp[i] = dp[i-1]+dp[i-2] print(dp[N]) 풀이 #2 (JavaScript) 풀이 #1과 마찬가지 방식으로 동작하며, 입력에 대한 결과값이 number 자료형의 범위를 벗어나므로 BigInt를 사용한다. const fs = require('fs'); const..

아이디어 회의 시간을 정렬하여 회의 시간이 겹치면 회의실 수를 증가시킨다. 풀이 #1 (Python) 회의 시작 시간과 끝나는 시간을 튜플로 오름차순 정렬하여 리스트 meeting에 저장한다. 리스트 time은 회의가 끝나는 시간들을 최소 힙의 형태로 저장하며, 처음에는 첫 회의가 끝나는 시간을 저장한다. for문에서는 두 번째 회의부터 시작 시간과 끝나는 시간을 각각 s와 e로, 가장 빨리 끝나는 이전 회의 시간을 t로 둔다. e를 우선 time에 추가한 후 s와 t를 비교해 회의 시간이 겹치면 t를 다시 추가하고, 그렇지 않으면 t는 time에서 제거한다. import sys, heapq input = sys.stdin.readline def solution(): N = int(input()) mee..

아이디어 거리가 먼 두 센서는 각각 다른 집중국과 통신하도록 한다. 풀이 #1 (Python) 오름차순 정렬된 센서 좌표를 리스트 sensor에 입력 받고, 센서 간 거리를 오름차순 정렬하여 리스트 D에 저장한다. N-1개의 센서 간 거리 중 가장 큰 값을 K-1개 제외할 수 있으므로 거리가 짧은 순으로 N-K개 값의 합을 출력한다. def solution(): N = int(input()) K = int(input()) sensor = sorted(map(int, input().split())) D = sorted([sensor[i+1]-sensor[i] for i in range(N-1)]) print(sum(D[:N-K])) solution() 풀이 #2 (JavaScript) 풀이 #1과 마찬가지..

아이디어 각 운동기구의 근손실 정도를 정렬하여 차례로 작은 값과 큰 값의 합 중 가장 큰 값을 출력한다. 풀이 #1 (Python) 근손실 정도를 오름차순 정렬 후 T에 저장하고, N이 홀수인 경우 결과값 res에 가장 큰 값을 pop하여 저장한다. for문에서 순서대로 작은 값과 큰 값의 합을 res와 비교하여 더 큰 경우 결과값을 갱신해 나간다. N = int(input()) T = sorted(map(int, input().split())) res = 0 if N%2: res = T.pop() for i in range(N//2): if T[i]+T[-(i+1)] > res: res = T[i]+T[-(i+1)] print(res) 풀이 #2 (JavaScript) 풀이 #1과 마찬가지 방식으로 동..

아이디어 양이 가장 많은 에너지 드링크에 나머지 에너지 드링크들을 모두 붓는다. 풀이 #1 (Python) N개의 에너지 드링크 양을 리스트 drink에 저장하고, 이들 합에 그 최댓값을 더하고 2로 나눈 값을 출력한다. N = int(input()) drink = tuple(map(int, input().split())) res = (sum(drink)+max(drink))/2 print(res) 풀이 #2 (JavaScript) 풀이 #1과 마찬가지 방식으로 동작한다. Math.max로 찾은 에너지 드링크 양 최댓값의 절반을 초기값으로 두고, reduce로 에너지 드링크들의 양을 반씩 더한다. const fs = require('fs'); const input = fs.readFileSync('/de..

아이디어 사전 순으로 가장 앞서는 수열이 되기 위한 규칙을 찾는다. 풀이 #1 (Python) 문어들이 1번과 2번 손을 번갈아 잡는 수열이 사전 순으로 가장 앞선다. 그러나 문어의 수가 홀수인 경우 1번과 2번 손만 사용해서는 원을 만들 수 없으므로 3번 손도 사용한다. 따라서 문어 수를 2로 나눠 소수점 이하를 버린 값만큼 1과 2가 담긴 리스트를 반복하고, 홀수면 3도 추가해 언패킹한다. N = int(input()) print(*[1, 2]*(N//2)+[3]*(N%2)) 문자열로 구현할 수도 있는데, 짝수인 경우 끝에 공백이 생기므로 rstrip 메서드로 공백을 제거한다. print(('1 2 '*(N//2)+'3'*(N%2)).rstrip()) 풀이 #2 (JavaScript) 입력으로 주어지..

자바스크립트의 비교 연산자는 보다 큼(>), 작음(=), 작거나 같음( 1); // true alert(2 == 1); // false alert(2 != 1); // true let result = 3 > 4; alert(result); // false 문자열은 유니코드 순으로 비교하며, 유니코드 순으로 인덱스가 더 큰 문자열이 더 크다고 판단된다. 두 문자열의 글자들을 차례로 비교하여 글자가 더 크거나 작은 문자열이 다른 문자열보다 크거나 작다고 판단되고, 비교가 끝날 때까지 결론이 나지 않으면 길이가 더 긴 문자열이 더 큰 것으로, 길이가 같다면 두 문자열은 같다고 판단된다. alert('Z' > 'A'); // true alert('Glow' > 'Glee'); // true alert('Bee'..