[SWEA] 8016. 홀수 피라미드
문제 경표는 아래와 같이 삼각형 모양으로 숫자를 쌓기로 했다. 1층에는 1개, 2층에는 3개, 3층에는 5개, … 와 같이 쌓는다. 위와 같이 경표는 끝도 없이 피라미드를 쌓을 때, N층의 제일 왼쪽, 오른쪽에 쓰게 될 숫자가 무엇일지 예측해보자. 풀이방법 처음에는 동적계획법(DP, Dynamic Programming) 알고리즘을 사용해 풀었으나 제출 시에 시간초과가 발생했다. 이유는 입력으로 n이 최대 10^9까지 입력되는데 이럴 경우 반복문은 1,000,000,000을 돌아야하므로 시간초과가 발생한다. 다른 방법으로 접근하면 왼쪽 가장자리의 수와 오른쪽 가장자리의 수들을 일정한 규칙을 가지는 수열로 생각하는 것이다. 왼쪽 가장자리 : 1, 3, 9, 19, .... 오른쪽 가장자리 : 1, 7, 17..
2020. 2. 28.
[SWEA] 3307. 최장 증가 부분 수열
문제 주어진 두 수열의 최장 증가 부분 수열(Longest Increasing Subsequence)의 길이를 계산하는 프로그램을 작성하시오. 수열 { A1, A2, ... , AN }의 최장 증가 부분 수열 B는 다음과 같이 정의된다. { B1, B2, ... , BK }에서 0≤K≤N, B1 ≤ B2 ≤ ... ≤ BK이고, AB1 ≤ AB2 ≤ ... ≤ ABK인 최대 K로 구성된 수열이다. 예를 들어, 수열이 { 1, 3, 2, 5, 4, 7 } 이라면, 최장 부분 증가 수열의 길이는 4가 된다. 풀이방법 동적 계획법(DP, Dynamic Programming)을 이용해서 해결할 수 있다. 입력된 수열의 길이와 같은 배열을 하나 선언하고 배열에 i번째 원소에는 수열의 i번째 원소까지의 최장길이가 ..
2020. 2. 27.
[SWEA] 4698. 테네스의 특별한 소수
문제 테네스는 소수를 좋아한다. 소수란 1과 자기 자신만으로 나뉘어 떨어지는 숫자로 작은 것부터 나열하면 2, 3, 5, 7, 11, 13, 17, 19, 23, …같은 수들이 있다. 또한 테네스는 D를 포함하는 숫자도 좋아한다. 그렇기에 소수가 D를 포함하면 더욱 더 좋아하여 특별한 소수라고 부르기로 했다. 예를 들어 D = 3이면 3, 13, 23, … 같은 소수들이 3을 포함하였으므로 테네스는 이런 숫자들을 특별한 소수라고 부를 것이다. D가 주어질 때, A이상 B이하의 수 중에서 특별한 소수인 것들의 개수를 구하는 프로그램을 작성하라. 풀이방법 D, A, B가 입력될 때마다 A부터 B까지의 소수를 구하면 시간초과가 발생한다. 따라서 1부터 B의 최대값 1000000까지 에라토스테네스의 체를 이용해..
2020. 2. 27.
