PRESENT

문제 설명 2016년 1월 1일은 금요일입니다. 2016년 a월 b일은 무슨 요일일까요? 두 수 a ,b를 입력받아 2016년 a월 b일이 무슨 요일인지 리턴하는 함수, solution을 완성하세요. 요일의 이름은 일요일부터 토요일까지 각각 SUN,MON,TUE,WED,THU,FRI,SAT 입니다. 예를 들어 a=5, b=24라면 5월 24일은 화요일이므로 문자열 "TUE"를 반환하세요. 제한 조건 2016년은 윤년입니다. 2016년 a월 b일은 실제로 있는 날입니다. (13월 26일이나 2월 45일같은 날짜는 주어지지 않습니다) 입출력 예 a b result 5 24 "TUE" 문제풀이 윤달은 2월이 29일까지 있는 날입니다. a월 b일의 요일을 구하기 위해선 1월부터 a-1월까지의 날 수를 더하고 b..

문제 S사에서는 각 부서에 필요한 물품을 지원해 주기 위해 부서별로 물품을 구매하는데 필요한 금액을 조사했습니다. 그러나, 전체 예산이 정해져 있기 때문에 모든 부서의 물품을 구매해 줄 수는 없습니다. 그래서 최대한 많은 부서의 물품을 구매해 줄 수 있도록 하려고 합니다. 물품을 구매해 줄 때는 각 부서가 신청한 금액만큼을 모두 지원해 줘야 합니다. 예를 들어 1,000원을 신청한 부서에는 정확히 1,000원을 지원해야 하며, 1,000원보다 적은 금액을 지원해 줄 수는 없습니다. 부서별로 신청한 금액이 들어있는 배열 d와 예산 budget이 매개변수로 주어질 때, 최대 몇 개의 부서에 물품을 지원할 수 있는지 return 하도록 solution 함수를 완성해주세요. 제한사항 d는 부서별로 신청한 금액이..

문제 정수 배열 numbers가 주어집니다. numbers에서 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아 return 하도록 solution 함수를 완성해주세요. 제한사항 numbers의 길이는 2 이상 100 이하입니다. numbers의 모든 수는 0 이상 100 이하입니다. 입출력 예 numbers result [2,1,3,4,1] [2,3,4,5,6,7] [5,0,2,7] [2,5,7,9,12] 입출력 예 설명 입출력 예 #1 2 = 1 + 1 입니다. (1이 numbers에 두 개 있습니다.) 3 = 2 + 1 입니다. 4 = 1 + 3 입니다. 5 = 1 + 4 = 2 + 3 입니다. 6 = 2 + 4 입니다. 7 = 3 + 4 입니다...

문제 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다. 전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성..

문제 풀기 : 1463번 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 구하라. 문제풀이 1로 만들기 위한 연산의 최소 사용 횟수를 구하는 문제이다. 하나의 숫자에 3가지 연산을 계속해서 수행해야 하기 때문에 중복연산이 동반되어 DP로 푸는 것이 좋다. 최적의 연산 횟수를 저장하는 DP 테이블을 생성한다. 현재의 정수X에 연산이 수행될 때..

문제 풀기 : 11727번 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. 문제풀이 다음은 n = 4 까지의 경우의 수를 따져본 것이다. +추가) n = 2일때 2x1을 2개 이어붙인 부분과 1x2를 2개 이어붙인 부분은 같은 모양으로 n=2의 경우의 수는 3가지가 아니라 2가지가 맞습니다! 그림을 잘못 그렸습니다. 참고해주세요!! n = 3 부터 보면 n = 2과 n = 1..

문제 풀기 : 11726번 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하라. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 문제풀이 다음은 n = 4 까지의 경우의 수를 따져본 것이다. n = 3 부터 보면 n = 1과 n = 2의 타일 모양이 그대로 들어있고 n = 4 를 보면 n = 2와 n = 3의 타일 모양을 그대로 가지고 있다는 것을 알 수 있다. 해당 규칙을 파악한대로 점화식을 작성해보면 dp[i] = dp[i-2] + ..

문제 풀기 : 10844번 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 45656이란 수를 보자. 이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하라. 0으로 시작하는 수는 없다. 문제풀이 길이가 N일 때 앞뒤로 차이가 1이 나는 숫자가 몇 개인지를 구하는 문제이다. 뒤에 있는 숫자를 기준으로 앞에 올 수 있는 숫자의 경우의 수를 구할 것이다. 자리수마다 각각의 숫자 앞에 올 수 있는 경우의 수가 다르므로 2차원 DP 테이블을 만든다. dp[ N의 수 ][ N 자리 숫자일 때 해당 숫자 앞에 올 수 있는 일의 자리 수 ] ..

문제 풀기 : 11057번 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 문제 오르막 수는 수의 자리가 오름차순을 이루는 수. 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하라. 수는 0으로 시작할 수 있다. 문제풀이 DP 테이블을 2차원 배열로 만든다. dp[ N의 수 ][ N 자리 숫자일 때 해당 숫자 앞에..

문제 풀기 : 2193번 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 문제 이친수는 1. 0과 1로만 이루어진 수 2. 0으로 시작하지 않는다. 3. 1이 두 번 연속으로 나타나지 않는다. N(1 ≤ N ≤ 90) N자리 이친수의 개수를 구하라. 문제풀이 n = 5 까지의 케이스를 찾아본다. n = 4(하늘색 표시) 부터 살펴보면 n = 2와 n =3의 경우의 수가 다 들어가 있는 것을 볼 수 있다. → 10, 00, 01 n = 5(빨간색 표시) 부터 살펴보면 n = 3와 n =4의 경우의 수..