[BOJ] 1476번 - 날짜 계산
문제설명 https://www.acmicpc.net/problem/1476 1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타 www.acmicpc.net 사고과정 E, S, M 을 while 무한 루프에서 하나씩 증가시키면서 주어진 E, S, M 과 같아질 때 break하면 된다. 단, 무한 루프 안에서 E, S, M 모두 1일 때 break하는 조건을 먼저 넣어준다. 그리고 s, e, m 과 연도를 1씩 증가시킨 후, s, e, m의 주어진 범위에 넘어가면 1로 바꾸어 준 후, e == E, s == S, m == M인지 조건을 확인한 후 b..
[BOJ] 11722번 - 가장 긴 감소하는 부분 수열
문제설명 https://www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net 사고과정 가장 긴 증가하는 부분 수열을 찾는 LIS 알고리즘을 이용하되 주어진 배열을 reverse 해서 LIS를 적용하거나 LIS 알고리즘 내부의 부등호를 반대로 바꾸어주면 된다. 예전에도 관련 문제를 풀어봐서 수월히 해결했다. 풀이 n = int(input()) array = list(map(int, input..
[BOJ] 11055번 - 가장 큰 증가 부분 수열
문제설명 https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수 www.acmicpc.net 사고과정 LIS 알고리즘을 활용하는데, 문제에서 요구하는 것은 증가하는 부분 수열의 합이 가장 큰 것을 구하는 것이다. 무의식적으로 그냥 증가 부분 수열의 길이를 DP 테이블에 넣고 삽질하고 있었다.. 문제에서 요구하는 것은 길이가 아닌 수열의 합이므로 DP 테이블에는 수열의 길이가 아닌 수열의 각 번째 자리에서 나올 수 있는 ..
[BOJ] 11057번 - 오르막 수
문제설명 https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 사고과정 이 문제도 DP 테이블을 2차원 리스트로 정의해야 한다. 이 때, 행($i$)는 N을, 열($j$)는 가장 앞에 오는 숫자 0~9를 의미한다. 결국 DP 테이블에 들어가는 값은 앞에오는 숫자가 0~9 중 하나일 때, 만들 수 있는 오르막 수 개수를 의미한다. N = 1일 때는 즉, 0~9까지 모두 1개밖에 존재하지 않는다. N = 2일 때는 앞..
