우노

문제 링크 https://www.acmicpc.net/problem/11726 풀이 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 타일은 1x2 이나 2x1 타일 중 한가지 종류만 사용해서 채워도 괜찮습니다. 해당 문제는 단순한 점화식으로 해결할 수 있습니다. dp[i] = dp[i-1] + dp[i-2] 세부 알고리즘은 아래 예제 코드와 같습니다. 코드 import sys n = int(sys.stdin.readline()) # dp 테이블 dp = [0] * 1001 # 초기값 설정 dp[1] = 1 dp[2] = 2 # bottom-up 진행 for i in range(3, n+1): dp[i] = dp[i-1] + dp[i-2] print(dp[..

문제 링크 https://www.acmicpc.net/problem/1913 풀이 외각의 크기에 따라, 가운데 좌표를 시작점으로 상하좌우로 이동하는 횟수를 일반화할 수 있습니다. 시작점을 기준으로, 진행순서는 상 → 우 → 하 → 좌 → 상이며, 진행횟수는 n에 따라, 상 n번, 우 n-2번, 하 n-1번, 좌 n-1번이 됩니다. 또한, 진행하고 있는 외각의 크기에 따라 시작점이 항상 (n//2, n//2) 이 될 수 있도록 n을 조절해야합니다. 예를 들어, n이 7로 주어진다면, 현재 진행하고 있는 외각이 변경됨에 따라 시작좌표를 (3, 3) → (2, 2) → (1, 1)로 변경해야합니다. 세부 알고리즘은 아래 코드와 같습니다. 코드 import sys # 자연수 N 입력 n = int(sys.std..

문제 링크 https://www.acmicpc.net/problem/1212 풀이 파이썬 내장함수를 사용하면 됩니다. 입력을 8진수로 변환한 뒤, bin()을 통해 2진수로 변환하고, 맨 앞의 '0b'를 제외한 나머지를 출력하면 됩니다. 추가적으로, 각 숫자가 8 이상인 입력은 들어오지 않습니다. 코드 import sys # 입력을 8진수로 변환 n = int(sys.stdin.readline().rstrip(), 8) # 8진수를 2진수로 변환한 뒤, 맨 앞의 '0b'를 제외한 나머지 출력 print(bin(n)[2:])

문제 링크 https://www.acmicpc.net/problem/21608 풀이 주어진 조건에 따라 순서대로 구현하면 되지만, 조건문에 따라 학생을 앉힐 수 있는 좌석을 비교하는 방법보단, 모든 비어있는 칸을 중심으로 인접한 칸들을 탐색하며, [좋아하는 학생의 수, 비어있는 칸의 개수, 중심 칸의 행 번호, 중심 칸의 열 번호]를 저장하고, 모든 칸을 탐색했을 때, 위 리스트에 대해, 좋아하는 학생의 수와 비어있는 칸의 개수는 내림차순으로 정렬하고, 중심 칸의 행 번호와 중심 칸의 열 번호는 오름차순 정렬한 뒤, 리스트의 가장 첫번째 요소의 행과 열 위치에 해당 학생을 앉히는 방법이 더 효율적입니다. 코드 import sys n = int(sys.stdin.readline()) # 자리 정보 seat..

문제 링크 https://www.acmicpc.net/problem/1339 풀이 해당 문제를 일반화하기 위해선, 각 알파벳의 자릿수를 기억해야합니다. 예를 들어, GCF + ACDEB 가 주어졌을 때, 각 알파벳의 자릿수를 별도로 저장합니다. A는 만의 자릿수를 가지기 때문에 10000 C는 천의 자릿수와 십의 자릿수를 둘 다 가지기 때문에 1010 G는 백의 자릿수를 가지기 때문에 100 D는 백의 자릿수를 가지기 때문에 100 E는 십의 자릿수를 가지기 때문에 10 B는 일의 자릿수를 가지기 때문에 1 F도 일의 자릿수를 가지기 때문에 1 이렇게 알파벳의 자릿수를 별도로 저장한 뒤, 자릿수를 내림차순 정렬하고, 자릿수가 높은 순서대로 숫자를 감소시켜가며 곱셈을 진행합니다. A = 10000 * 9 ..

문제 링크 https://www.acmicpc.net/problem/16953 풀이 B를 A로 바꾸는 방식으로 진행한다. B가 2로 나눠진다면, B를 2로 나누고 나눠지지 않으며, B의 가장 오른쪽이 1이라면, 가장 오른쪽에서 1을 제거한다. B가 2로 나눠지지도 않고, 가장 오른쪽이 1이 아닌 경우도 있다는 것을 주의해야한다. 코드 import sys # A와 B 입력 a, b = map(int, sys.stdin.readline().split()) # 변환 횟수 count = 1 # A보다 B가 클때까지 while (a < b): # B가 2로 나눠진다면, B를 2로 나누고 if (b % 2 == 0): b = b // 2 # 나눠지지 않는다면, else: # B의 가장 오른쪽이 1이라면 if (in..

문제 링크 https://www.acmicpc.net/problem/10610 풀이 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다. 102에 포함된 숫자는 1, 0, 2이며, 30의 배수가 되는 가장 큰 수는 210(2, 1, 0)이다. 이 문제는 해당 수가 30의 배수가 되는 조건을 알아야 풀 수 있으며, 30의 배수가 되는 조건은 아래와 같다. 일의 자리가 0이어야한다. 따라서, 받은 숫자 내에 0이 없다면 -1을 출력해야한다. 각 자리의 숫자들을 모두 더했을 때, 3으로 나누어 떨어져야한다. 따라서, 받은 숫자들의 합이 3으로 나누어 떨어지지 않는다면 -1을 출력해야한다. 두 조건을 통과했을 때, 주어진 숫자들을 내림차순 정렬한다면, 30의 배수가 되는..

문제 링크 https://www.acmicpc.net/problem/1931 풀이 주어진 시작 시간과 종료 시간들을 이용해서 가장 많은 회의의 수를 알기 위해서는, 회의가 빨리 끝나는 순서대로 정렬을 진행해야 한다. 회의가 빨리 끝날수록 뒤에서 고려할 수 있는 회의가 많기 때문이다. 만약, 회의가 빨리 시작하는 순서대로 정렬을 진행한다면, 오히려 회의가 늦게 끝날 수도 있다. 또한, 회의가 끝나는 시간이 같을 경우엔, 회의가 빨리 시작하는 순서대로 정렬을 진행해야한다. 예를 들어, 회의가 (2, 2), (1, 2) 순서대로 주어진다면, (2, 2) 회의만 진행할 수 있지만 (1, 2), (2, 2) 순서대로 주어진다면, (1, 2), (2, 2) 회의를 모두 진행할 수 있기 때문이다. 따라서, 주어진 회..

문제 링크 https://www.acmicpc.net/problem/1759 풀이 사용할 문자들을 입력 받아, 모음과 자음 리스트에 추가합니다. i를 1부터 l-2까지 증가시키며, 모음 리스트에서 i개의 모음을 뽑는 조합과 자음 리스트에서 l-i개의 자음을 뽑는 조합을 생성합니다. 이후, 모음 조합과 자음 조합의 각 요소들을 결합한 뒤, 정렬하고, 결과 리스트에 추가합니다. 알고리즘에 대한 세부 설명은 아래 코드와 같습니다. 코드 import sys from itertools import combinations # 결과 문자열 길이 l과 알파벳 개수 c l, c = map(int, sys.stdin.readline().split()) # 모음 전체 temp = [&#39;a&#39;, &#39;e&#39..

문제 링크 https://www.acmicpc.net/problem/1929 풀이 에라토스테네스의 체를 이용해야하는 대표적인 문제입니다. m의 값이 최소 1인 것을 주의해야하며, n의 값이 최대 1000000인 것을 주의해야합니다. 또한, 소수 탐색 시, n의 제곱근까지만 탐색을 진행한다면 실행 시간을 단축시킬 수 있습니다. 코드 import sys import math # m과 n 입력 m, n = map(int, sys.stdin.readline().split()) # 소수 판별 결과를 저장하기 위한 리스트 초기화 # 처음에는 모든 수가 소수인 것으로 초기화 array = [True] * (1000001) # 1은 소수가 아님 array[1] = False # 2부터 n의 제곱근까지 에라토스테네스의 ..