![]()
문제 설명 매 초 바이러스가 인접한 칸으로 전염되고, 바이러스의 번호가 낮은 순부터 먼저 증식한다. 따라서 최소 힙을 구성하여 현재 바이러스의 시간과 번호를 차례로 넣어주면, 바이러스 중에서 시간이 가장 적은 바이러스가 먼저 선택되고, 같은 시간 내에서는 낮은 번호부터 선택된다. 풀이 import sys, heapq input = sys.stdin.readline DIR = [(1,0), (-1,0), (0,-1),(0,1)] def bfs(graph, n, s): que = [] # (흐른 시간, 바이러스 레벨, y좌표, x좌표) for i in range(n): for j in range(n): if graph[i][j] > 0: heapq.heappush(que, (0, graph[i][j], i,..
문제 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000) 출력 문제의 조건을 만족하는 쌍의 개수를 출력한다. 예제 입력 1 9 5 12 7 10 9 1 2 3 11 13 예제 출력 1 3 해결 먼저 수열의 크기와 수열, 합을 입력 받고, 수열을 오름차순으로 정렬한다. 투포인터를 이..
![]()
문제 https://www.acmicpc.net/problem/11726 기본 풀이 해당 문제는 dp로 풀 수 있습니다. 하나씩 채워 나간다고 생각했을 때, 채울 수 있는 방법은 2가지입니다. 세로 직사각형 채우기, 가로 직사각형 채우기입니다. 하지만, 가로 직사각형은 칸을 채우기 위해 가로 직사각형을 겹쳐서 2개씩 (정사각형 모양으로) 채워야만 합니다. 1. 두 단계 전(dp[i-2]) + 정사각형(가로 직사각형 두 개) 2. 한 단계 전(dp[i-1]) + 직사각형(세로 직사각형 한 개) 이렇게 두 가지로 나눠볼 수 있기에, dp[i] = dp[i-2]+dp[i-1] 의 반복으로 구할 수 있습니다 코드 풀이 그러나, 고민을 해보면 다른 수학적 방법이 있습니다. 직관적으로 가장 간단하게 채우는 법은 세..
문제 https://www.acmicpc.net/problem/14916 설명 - DP (다이나믹 프로그래밍) - 1부터 9까지의 숫자 중에서 -1이 나오는 경우는 1과 3밖에 없다. 그리고 나머지 값들에 대해서는 미리 해당하는 동전 개수를 할당해주었고, 10부터의 숫자는 동일한 규칙을 발견할 수 있다. 10원 : 5원 * 2 + 2원 * 0 => (5원) + 1개 11원 : 5원 * 1 + 2원 * 3 => (6원) + 1개 12원 : 5원 * 2 + 2원 * 1 => (7원) + 1개 . . 코드 n = int(input()) # 0 1 2 3 4 5 6 7 8 9 dp = [-1, -1, 1, -1, 2, 1, 3, 2, 4, 3] for i in range(10, n+1): dp.append(dp..
https://www.acmicpc.net/problem/14495 14495번: 피보나치 비스무리한 수열 피보나치 비스무리한 수열은 f(n) = f(n-1) + f(n-3)인 수열이다. f(1) = f(2) = f(3) = 1이며 피보나치 비스무리한 수열을 나열하면 다음과 같다. 1, 1, 1, 2, 3, 4, 6, 9, 13, 19, ... 자연수 n을 입력받아 n번째 피보 www.acmicpc.net 유형 다이나믹 프로그래밍 문제 피보나치 비스무리한 수열은 f(n) = f(n-1) + f(n-3)인 수열이다. f(1) = f(2) = f(3) = 1이며 피보나치 비스무리한 수열을 나열하면 다음과 같다. 1, 1, 1, 2, 3, 4, 6, 9, 13, 19, ... 자연수 n을 입력받아 n번째 피보..
https://www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 문제요약 거스름돈 금액이 입력으로 주어지고, 5원과 3원으로 해당금액을 만들 때, 만들수 있으면 동전의 최소 개수를, 만들 수 없으면 -1을 출력 문제해결 일단 5원을 가장 많이 사용하고 싶다고 생각할 수 있다. 예를 들어 23원을 계산한다고 했을 때, 5x4 + 3이 되는데 이는 안되므로 5x3 + 8이 된다. 이를 좀 더 바꿔서 dynamic programming을 적용시킨다고하면, 23은 5를 일단 하나 사용하고, 나머지 18(=23-5)을 만들수 있는 방법에 1을 더한다고 생각할 수 있다. 따라서 dp[i]를..
https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 코드 #include #include #include #include #include #include #include #include #include #include #include #define LL long long using namespace std; LL arr[500][500]; int main() { int n = 0; int m = 0; LL b = 0; cin >> n >> m >..
![]()
풀이:. A,B,C,D를 입력받는다.// A와 B, C와 D를 각각 E,F(문자열)로 합친다// E, F 를 정수형으로 바꾼다.// E와 F를 합친 것을 출력한다
![]()
문제 프로야구팀 울림 제미니스는 오늘도 졌다. 이번에는 스타트링크 걸리버스의 4번타자가 끝내기 홈런을 쳐서 졌다. 울림 제미니스의 열렬한 팬인 지수는 속으로 화를 참으며 어떤 선수 때문에 졌는지 생각해보았다. 지수는 팀이 역전패를 했다면 불펜 투수의 책임이고, 그렇지 않다면 타자와 선발 투수의 책임이라고 생각했다. 지수는 오늘 경기에서 울림이 어떻게 졌는지 생각해보려 했지만, 기분이 너무 더러워서 뭘 할 의욕이 나지 않았다. 지수를 도와 오늘 경기에서 울림 제미니스가 역전패를 했는지 구하는 프로그램을 작성하여라. 역전패가 성립하려면 경기 도중 울림 제미니스가 이기고 있는 순간이 있어야 한다. 입력 첫 번째 줄에는 9개의 정수가 주어지는데, 오늘 경기에서 울림 제미니스가 1회 초, 2회 초, ..., 9회..
![]()
문제 도깨비말은 언어 유희 중 하나로, 글자를 특정 법칙에 따라 재구성하는 것을 말한다. 영어권에서는 피그라틴어라는 것이 있다. 주로 어린이들이 많이 쓰는 데, 남들에게 무슨 말인지 모르게 하기 위해 종종 쓴다. 여기엔 규칙이 있는데, 맨 앞글자가 모음이 아닐때 까지 맨 앞 글자를 어미로 돌린 후 그 끝에 ay를 붙여서 완성한다. 예를 들면 frog는 ogfray이 된다. 만약 맨 앞자음이 없는 apple과 같은 경우는 끝에 ay만 붙여 appleay가 된다. 또는, 단어에 모음이 없는 경우에도 단어의 끝에 ay만 붙인다. 주어진 단어를 피그라틴어로 바꾸는 프로그램을 작성하시오. 입력 한 줄에 하나의 단어씩 주어진다. 그리고 마지막 줄에 #을 입력받고 끝낸다. 주어진 단어는 20자를 넘지 않고 공백없이 ..
![]()
문제 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다. 여러분은 입력으로 주어진 괄호 문자열..
![]()
문제 강민이는 치킨 한 마리를 주문할 수 있는 치킨 쿠폰을 n장 가지고 있다. 이 치킨집에서는 치킨을 한 마리 주문할 때마다 도장을 하나씩 찍어 주는데, 도장을 k개 모으면 치킨 쿠폰 한 장으로 교환할 수 있다. 강민이가 지금 갖고 있는 치킨 쿠폰으로 치킨을 최대 몇 마리나 먹을 수 있는지 구하여라. 단, 치킨을 주문하기 위해서는 반드시 치킨 쿠폰을 갖고 있어야 한다. 입력 여러 줄에 걸쳐서 자연수 n과 k가 주어진다. 출력 각 입력마다 한 줄에 정답을 출력한다. 제한 1 < k ≤ n ≤ 1,000,000,000 예제 입/출력 코드 풀이 1. 우선 입력값에 제한이 없기때문에 EOFError가 나면 코드가 멈추도록 while문 안에 try/except 를 사용 2. 들고있는 치킨쿠폰 N과 치킨으로 바꾸는..
