CEO

N과 M 시리즈 원소가 1에서 N인 경우 15649 N과 M (1) 15650 N과 M (2) 15651 N과 M (3) 15652 N과 M (4) 원소가 주어지는 경우 N과 M (5 ~ 8) N과 M (1 ~ 4)에서 원소에 대한 처리만 추가하면 된다. 중복 원소가 존재하는 경우 15663 N과 M (9) N과 M (10 ~ 12)는 (9)와 같이 set을 활용하며 로직은 N과 M 2 - 4와 동일하다. 문제 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 풀이 이전에 다룬 문제인 15649 N과 M ..

N과 M 시리즈 원소가 1에서 N인 경우 15649 N과 M (1) 15650 N과 M (2) 15651 N과 M (3) 15652 N과 M (4) 원소가 주어지는 경우 N과 M (5 ~ 8) N과 M (1 ~ 4)에서 원소에 대한 처리만 추가하면 된다. 중복 원소가 존재하는 경우 15663 N과 M (9) N과 M (10 ~ 12)는 (9)와 같이 set을 활용하며 로직은 N과 M 2 - 4와 동일하다. 문제 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 풀이 N개의 자연수에서 길이가 M인 수열을 구..

문제 3085번: 사탕 게임 문제 상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다. 가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고 www.acmicpc.net 문제 풀이 인접한 사탕을 swap 하고, 가로 세로에서 연속된 사탕의 개수를 체크하면 해당 문제를 풀 수 있다. 다음과 같은 경우의 수를 판단하여 문제를 접근하면 쉽게 해결할 수 있다. 또한 swap 되는 경우 모든 범위를 탐색하는 것이 아닌, swap 되는 영역만 탐색한다면 속도를 높일 수 있을 것 같다. 대각선은 인접한것으로 판단하지 않는다. 즉, 가로 세로에 대한 swap만 처리하고 비교하면 된다. N의 크기가 50이므로 브루트 포스로 충..

문제 6064번: 카잉 달력 문제 최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있� www.acmicpc.net 문제 풀이 첫 번째 해의 범위가 M, 두 번째 해의 범위가 N이고 현재 년도가 각각 x, y로 주어질 때 몇 번째 해인지 찾는 문제이다. 또한 N, M을 통해 세상의 종말이 도래하는 마지막 해를 구하여야 하는데 이는 N, M의 최소 공배수이다. 예시와 같이 M, N, x, y은 10, 12, 3, 9의 경우 다음과 같이 해당 연도를 구할 수 있다. x y 3 3 % 12 = 3 13 13 % 12 = 1 23 23 % 12 = 11 33 33 % 12 = 9 ..

문제 1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타�� www.acmicpc.net 문제 풀이 지구, 태양, 달의 수 범위는 각각 15, 28, 19로 다르다. 그러면 지구, 태양, 달의 수가 주어졌을 때 이를 통해 년도를 구하는 방법은 간단하다. 현재 연도 - 지구의 수, 현재 연도 - 태양의 수, 현재 연도 달의 수가 15, 28, 19로 각각 나누었을 때 모두 0이 되면 입력 값에 올바른 연도를 구할 수 있다. 코드 from sys import stdin if __name__ == '__main__': e, s, m = map(int,..

문제 1748번: 수 이어 쓰기 1 첫째 줄에 N(1≤N≤100,000,000)이 주어진다. www.acmicpc.net 문제 풀이 브루트 포스로 풀면 시간 초과로 풀지 못한다. 그렇다면 어떻게 효율적으로 구할 수 있을까? 다음과 같은 경우를 생각해보면 쉽게 구할 수 있다. 자릿수는 몇 자릿수 인지를 의미한다. 예를 들어 1 ~ 9는 한 자릿수이다. 1 ~ 9 : 9개 * 자릿수 10 ~ 99 : 90개 * 자릿수 100 ~ 999 : 900개 * 자릿수 즉, 120의 경우 9 + 180 + ? 가 된다. 그럼 100과 120의 사이의 수들도 계산할 수 있다. (120 - 100 + 1) * 자릿수가 된다. 100과 120 사이의 값들 계산에서 +1을 해주는 것은 100도 포함되기 때문이다. 이와 같이 ..

문제 13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 문제 풀이 이전에 풀었던 1912 연속합에서 하나의 숫자를 뺄 수 있는 조건이 추가된 문제이다. 따라서 문제 풀이는 다음과 같이 접근할 수 있다. 아무것도 빼지 않는 연속합을 메모 이제이 션 한다. 구해진 연속합에서 중간에 수를 제거한 경우에 대한 값을 메모이제이션 한다. 1번의 경우는 연속합 문제에서 다루었다. 그럼 2번의 경우는 어떤식으로 찾을 수 있을까? 조금만 생각해보면 쉽게 답을 찾을 수 있다. 예를 들어 4개의 값이 있다면 OOXO와 같이 2번 인덱스..

문제 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제 풀이 메모이제이션을 잘 활용하면, 어렵지 않게 풀 수 있다. 또한 각 N행은 하나의 집을 나타내고 1, 2, 3열은 R, G, B로 칠 할 경우 발생하는 비용을 의미한다. 기본 예제는 그림과 같이 나타낼 수 있다. 집 1(0번 인덱스)은 첫 번째 집이기에 값을 누적시킬 필요가 없다. 따라서 집 2(1번 인덱스)부터는 해당 색상을 선택하였을 때, 이전의 집에서 선택할 수 있는 색상의 값 중 최솟값을 더한다. 이를 통해 집 2에 합산..