투투

www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 접근 분할정복이 이해가 되지않아 문제를 풀어보면서 이해하고자 했다. 분할정복은 큰 문제를 풀기보다 작은 문제들로 나누고 작은 문제부터 해결해나가는 것이라고 이해했다. 그래서 이 문제에서 어떻게 분할할지를 신경썼다. 다른 사람들의 풀이를 참고하였는데 입력예시처럼 8x8 크기의 맵이 들어온다고 해보자. 8x8의 크기를 4x4의 크기로 나눠 네 개의 맵을 만든다. 그리고 다시 4x4를 2x..

문제 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23) 자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스는 n을 포함하는 한 줄로 이루어져 있다. 입력의 마지막에는 0이 주어진다. 출력 각 테스트 케이스에 대해서, n보다 크고, 2n보다 작거나 같은 소수의 개수를 출력한다. 접근 에라토스테네스의 체로 123456x2까지의 소수를 구하여 N을 입력할 때마다 범위 내의 소..

문제 M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. 출력 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다. 접근 앞으로 n이 소수인지 판단을 할 때 2부터 n의 제곱근까지 검사를 하도록 하자. 왜냐하면 n의 약수는 n/2보다 크지 않기 때문이다. 구현 소수를 판별하는 함수인 is_prime()에서 전달받은 숫자의 제곱근까지 검사하여 소수를 판별하였다. def is_prime(number): if number == 1: return False for i in range(2, int(number**0.5)+1): if numb..

문제 정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오. 입력 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. 출력 N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다. 접근 소인수분해는 합성수를 소수의 곱으로 나타내는 것이다. 그래서 정수 N이 주어졌을 때 2부터 계속 나눠간다. 이후 2로 나누어 떨어지지 않는다면 수를 증가시켜 3으로 나눈다. 3으로 나누어 떨어지지 않는다면 4로 나누지만 이전에 2로 모두 나눴기 때문에 4로 나누어 떨어지지 않을 것이며 바로 5로 갈것이다. 이러한 원리로 N이 1이 될 때까지 반복한다. 구현 입력받은 N을 n으로 계속 나눠주며 나누어 떨어지지 않을 때 n을 증가시킨다. N = int(..

문제 M과 N사이의 소수를 찾아 소수들의 합과 소수들 중 최솟값을 출력한다. 입력 입력의 첫째 줄에 M이, 둘째 줄에 N이 주어진다. M과 N은 10,000이하의 자연수이며, M은 N보다 작거나 같다. 출력 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. 구현 M부터 N까지 탐색하여 1이 아닐 경우 소수인지 판별한다. 2부터 i전까지 나눴을 때 나누어 떨어진다면 소수가 아니다. 이 방식으로 소수를 판별하고 소수가 없을 때에는 -1을 출력하고 그렇지 않다면 합과 최솟값을 찾아 출력한다. M = int(input()) N = int(input()) prime_numbe..

문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 접근 처음에 위에서 주어진 조건대로 구현을 하려고 했지만 실패했다. 최소 연산을 해야하는 최적화문제이기 때문에 그리디 or 동적프로그래밍으로 풀 수 있겠다는 생각을 하였다. 하지만 여기서 그리디로 구현하면 최적해가 나올 수 없었고 동적프로그래밍을 사용하였다. 여기서 할 수..

문제 종말의 숫자란 어떤 수에 6이 적어도 3개이상 연속으로 들어가는 수를 말한다. 제일 작은 종말의 숫자는 666이고, 그 다음으로 큰 수는 1666, 2666, 3666, .... 과 같다. 따라서, 숌은 첫 번째 영화의 제목은 세상의 종말 666, 두 번째 영화의 제목은 세상의 종말 1666 이렇게 이름을 지을 것이다. 일반화해서 생각하면, N번째 영화의 제목은 세상의 종말 (N번째로 작은 종말의 숫자) 와 같다. 숌이 만든 N번째 영화의 제목에 들어간 숫자를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. 출력 N번째 영화제목을 출력한다. 접근 1탄은 666이고 2탄은 1666이다. 영화제목에는 666이 포함되어 있어야 한다. 처음에 입력된 N에 따라 출력을 만들어보려고 했지만 실..

www.acmicpc.net/problem/17779 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름 www.acmicpc.net 접근 x, y, d1, d2를 조건에 맞게 설정하고 5번 구역을 먼저 나눠준다. 그리고 다른 구역들은 5번을 경계선으로 하여 선거구 안에 있는 인원들을 더해준다. 이때 5번 쪽으로 인덱스가 증감하도록 하여 5번을 만났을 때 break를 걸어준다. 구현 import sys input = sys.stdin.readline def partition(x, y, d1, d2): # 5번 표시 cache = [[0 for _ ..

문제 집을 크기가 RxC인 격자판으로 나타냈고 1x1크기의 칸으로 나눴다. 각 칸에는 미세먼지 양이 적혀있고, 공기청정기는 항상 1번 열에 설치되어있으며 두 칸을 차지한다. 그리고 1초 동안 다음과 같은 일이 순서대로 일어난다. 1. 미세먼지가 확산된다. 확산은 모든 칸에서 동시에 일어난다. - 미세먼지는 인접한 네 방향으로 확산된다. - 인접한 방향에 공기청정기가 있거나 칸이 없으면 그 방향으로는 확산이 일어나지 않는다. - 확산되는 양은 해당 칸의 미세먼지양/5이다. - 확산되고 남은 미세먼지의 양은 원래 미세먼지양 - (미세먼지양/5 * 확산된 방향의 수)이다. 2. 공기청정기가 작동한다. - 공기청정기에서 바람이 나온다. - 위쪽 공기청정기의 바람은 반시계 방향으로 순환하고 아래쪽 공기청정기의 바..

문제 5개의 나무 조각에는 1부터 5까지 숫자 중 하나가 쓰여져 있다. 다음과 같은 과정을 거쳐 1, 2, 3, 4, 5 순서로 만들어보자. 1. 첫 번째 조각의 수가 두 번째 수보다 크다면, 둘의 위치를 서로 바꾼다. 2. 두 번째 조각의 수가 세 번째 수보다 크다면, 둘의 위치를 서로 바꾼다. 3. 세 번째 조각의 수가 네 번째 수보다 크다면, 둘의 위치를 서로 바꾼다. 4. 네 번째 조각의 수가 다섯 번째 수보다 크다면, 둘의 위치를 서로 바꾼다. 5. 만약 순서가 1, 2, 3, 4, 5 순서가 아니라면 1 단계로 다시 간다. 입력 첫째 줄에 나무 조각에 쓰여있는 수가 순서대로 주어진다. 출력 두 조각의 순서가 바뀔때 마다 조각의 순서를 출력한다. 문제에서 주어진 조건대로 구현을 한다. 구현 나무..