![]()
문제 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 특이점 처음엔 배열의 길이, 그 다음부터 각 줄마다 배열의 요소를 입력한다. 각 요소값은 1000 이하의 음이 아닌 정수. 포도주가 일렬로 나열된다. → 1차원 배열을 이용한다. 연속으로 3개의 수를 고를 수 없다. 총 합이 최대가 되는 수를 골라야한다. 위 조건들을 고려해봤을 때, 마지막 수를 포함한다고 무조건 최대값이 나오는 것은 아니다. 코드 cnt = int(input()) w = [0..
![]()
문제 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 특이점 스티커 당 점수 분포를 입력으로 결정한다. 입력은 2차원 배열 방식이다. 따라서 2차원 배열을 이용해야 함을 예상할 수 있다. 도출 가능한 모든 점수 중 최대 값이 2xn 개의 스티커 점수 최대값이 된다. 특정 스티커를 고를때, 좌, 우 , 상(or 하)에 있는 스티커는 선택 가능한 스티커에서 제외된다. 코드 cnt = int(input()) for i in range(cn..
![]()
문제 https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 특이점 이친수는 0으로 시작하지 않는다 == 앞자리가 무조건 1로 시작한다. 1이 두번 연속으로 나타나지 않는다 == 이친수가 2자리 이상일 경우, 앞 2자리는 무조건 10으로 시작한다. 반면에 00은 가능하다 → 10으로 시작하되, 1 다음에는 무조건 0이 나와야 함. 코드 import sys num = int(sys.stdin.readline()) dp=[[0]*2 for i ..
![]()
문제 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 특이점 계단수의 개념: 앞뒤 숫자와 차이가 1이나는 수들의 연속 맨 앞 숫자로 0이 오는건 불가능하지만, 중간이나 끝에 0이 위치하는 것은 가능하다. input은 계단의 길이, 즉 나열하는 숫자의 개수이다. output은 길이에 따라 가능한 경우의 수이다. 코드 import sys num = int(sys.stdin.readline()) #계단 수 담을 2차원 배열 dp[0~num][0~9] 생성 dp=[[0] * 10 for i in range(num+1)] #dp[0]=[0,0,0,0,0,0,0,0,0..
![]()
문제 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 특이점 오직 1, 2, 3의 합으로만 표현 가능하다. 잊으면 안됨! (사실 내 얘기임) 입력값은 특이하기 11 미만이라고 명시 해 놓았다. 따라서 범위는 0 < n < 11, n은 정수 이다. 입력 케이스마다 바로 대응하여, 방법의 수(=값)을 출력해야 한다. 코드 cnt = int(input()) for j in range(cnt): num = int(input()) way = [0]*(num+1) for i in range(1, num+1): if i == 1: way[i] = 1 el..
![]()
문제 https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 코드 num = int(input()) way = [0]*(num+1) for i in range(1, num+1): #입력값이 1일때 index error를 방지하기 위해 for문 안에서 함께 처리 if i == 1: way[i] = 1 elif i == 2: way[i] = 3 else: way[i] = way[i-1] + way[i-2]*2 print(way[num]%10007) 풀이 풀이 진행 방법은 그 전 문제인..
![]()
문제 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 코드 def factorial(k): total = 1 for i in range(2,k+1): total *= i return total result = [1] #인덱스 0 (=2*1타일이 0개인 경우)의 경우의 수는 무조건 1 num = int(input()) for i in range(1, (num//2)+1): v = factorial(num-i)//(factorial(i)*factorial(num-2*i..
문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 코드 mincal = [0,0] num = int(input()) for i in range(2,num+1): mincal.append(mincal[i-1]+1) if i%3 == 0: mincal[i] = min(mincal[i], mincal[i//3]+1) if i%2==0: mincal[i] = min(mincal[i], mincal[i//2]+1) print(mincal[num]) 풀이 처음에 if-elif를 이용했다가 오답이 나왔었다. mincal = [0,0] num = int(input())..
![]()
문제 https://www.acmicpc.net/problem/10992 10992번: 별 찍기 - 17 예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요. www.acmicpc.net - 출력 종류가 1층/ n층/ 나머지층 크게 3분류로 나뉨 코드 n = int(input()) for i in range(1, n+1): if i == 1: print(" "*(n-i)+"*") elif i == n: print("*"*(2*i-1)) else: print(" "*(n-i)+"*"+" "*(2*(i-2)+1)+"*") 풀이 출력 시 특이점이 있는 부분인 1층, n층에서의 출력문을 if- elif - else를 이용해 나눠줬다. n층을 제외한 나머지 층 i에서, 공백부분이 n-i만큼 먼저 나온 후, 양 끝에..
![]()
문제 https://www.acmicpc.net/problem/2446 2446번: 별 찍기 - 9 첫째 줄부터 2×N-1번째 줄까지 차례대로 별을 출력한다. www.acmicpc.net 코드 cnt = int(input()) #1번째~ 5번째 줄 for i in range(1,cnt+1): print(' '*(i-1)+'*'*(2*(cnt-i)+1)) #6번째~ 9번째 줄(1줄 적게) for j in range(2,cnt+1): print(' '*(cnt-j)+'*'*(2*j-1)) 풀이 무식하게 푼 감이 없지않아 있다... 그냥 직관적으로 *이 줄어드는 첫 번째 for문 과 다시 *이 증가하는 두번째 for문을 이어붙였다. 다른 풀이 출처: https://www.acmicpc.net/source/18..
문제 https://www.acmicpc.net/problem/8393 8393번: 합 n이 주어졌을 때, 1부터 n까지 합을 구하는 프로그램을 작성하시오. www.acmicpc.net 코드 cnt = int(input()) print(sum(i for i in range(1,cnt+1))) 풀이 간단하게 풀이가 가능해 보여서 직관적으로 풀었다. 이럴경우 시간 복잡도는 O(n). ✔ 하지만 수학적으로 접근하면 1~n 까지의 합은 n(n+1)/2 즉, (n^2 + n)/2 로 한번의 계산으로 도출 가능하며, 이때 시간 복잡도는 O(1)로 대폭 감소한다. ✔ 문제를 풀이할 때 여러 방향으로 생각해보자. 다른 풀이 출처: https://www.acmicpc.net/source/13249601 n = int(i..
![]()
문제 https://www.acmicpc.net/problem/1924 1924번: 2007년 첫째 줄에 빈 칸을 사이에 두고 x(1 ≤ x ≤ 12)와 y(1 ≤ y ≤ 31)이 주어진다. 참고로 2007년에는 1, 3, 5, 7, 8, 10, 12월은 31일까지, 4, 6, 9, 11월은 30일까지, 2월은 28일까지 있다. www.acmicpc.net - 2월이 28일까지 있다. - 1월 1일이 월요일이다. 코드 month = [31,28,31,30,31,30,31,31,30,31,30,31] days = ["SUN","MON","TUE","WED","THU","FRI","SAT"] m, d = map(int, input().split()) print(days[((sum(month[i] for i ..
