![]()
문제 땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다. 달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다. 달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B > a >> b >> v; n = (v-a)/(a-b); if((v-a)%(a-..
https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 코드 #include #include #include #include #include #include #include #include #include #include #include #define LL long long using namespace std; int dp[100][100001]; int main() { memset(d..
![]()
문제 올림픽은 참가에 의의가 있기에 공식적으로는 국가간 순위를 정하지 않는다. 그러나, 많은 사람들이 자신의 국가가 얼마나 잘 하는지에 관심이 많기 때문에 비공식적으로는 국가간 순위를 정하고 있다. 두 나라가 각각 얻은 금, 은, 동메달 수가 주어지면, 보통 다음 규칙을 따라 어느 나라가 더 잘했는지 결정한다. 금메달 수가 더 많은 나라 금메달 수가 같으면, 은메달 수가 더 많은 나라 금, 은메달 수가 모두 같으면, 동메달 수가 더 많은 나라 각 국가는 1부터 N 사이의 정수로 표현된다. 한 국가의 등수는 (자신보다 더 잘한 나라 수) + 1로 정의된다. 만약 두 나라가 금, 은, 동메달 수가 모두 같다면 두 나라의 등수는 같다. 예를 들어, 1번 국가가 금메달 1개, 은메달 1개를 얻었고, 2번 국가와..
https://www.acmicpc.net/problem/20057 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 문제요약 모래의 양이 표시된 격자가 있고, 토네이도가 격자 안을 돌아 나간다. 토네이도는 모래를 주어진 규칙에 맞게 흩뿌리면서 지나가는데, 이때 토네이도가 최종적으로 격자끝에 도달했을 때, 격자 바깥으로 나간 모래의 양을 구하는 시뮬레이션 문제 문제 해결 문제에서 흩뿌리는 정보가 토네이도 현재위치 기준으로 주어졌으므로, 먼저 토네이도의 위치변화를 문제의 주어진 조건..
![]()
문제 https://www.acmicpc.net/problem/13567 13567번: 로봇 입력은 표준 입력으로부터 받는다. 첫 줄에는 두 정수 M과 n (1 ≤ M ≤ 1,000, 1 ≤ n ≤ 1,000)이 주어진다. M은 정사각형 S의 한 변의 길이, 즉 오른쪽 맨 위의 좌표는 (M, M)이 된다. n은 로봇이 수행할 www.acmicpc.net Algorithm n개의 명령어 이후에 로봇의 위치를 출력하는 문제이다. 만약 로봇이 구역을 벗어난다면 -1을 출력하도록 구성해야 한다. 로봇이 구역을 한번이라도 벗어난다면 -1을 출력해야 하므로 명령어가 입력될때마다 현재 위치를 확인하여 판단해주어야 하므로 flag변수를 이용하여 판단하였다. 로봇이 MOVE명령어를 입력받으면 해당 칸수만큼 현재 바라보고..
1417번: 국회의원 선거 (acmicpc.net) 1417번: 국회의원 선거 첫째 줄에 후보의 수 N이 주어진다. 둘째 줄부터 차례대로 기호 1번을 찍으려고 하는 사람의 수, 기호 2번을 찍으려고 하는 수, 이렇게 총 N개의 줄에 걸쳐 입력이 들어온다. N은 50보다 작거나 같 www.acmicpc.net 문제유형 *시뮬레이션 문제 다솜이는 사람의 마음을 읽을 수 있는 기계를 가지고 있다. 다솜이는 이 기계를 이용해서 2008년 4월 9일 국회의원 선거를 조작하려고 한다. 다솜이의 기계는 각 사람들이 누구를 찍을 지 미리 읽을 수 있다. 어떤 사람이 누구를 찍을 지 정했으면, 반드시 선거때 그 사람을 찍는다. 현재 형택구에 나온 국회의원 후보는 N명이다. 다솜이는 이 기계를 이용해서 그 마을의 주민 M..
![]()
문제 설명 매 초 바이러스가 인접한 칸으로 전염되고, 바이러스의 번호가 낮은 순부터 먼저 증식한다. 따라서 최소 힙을 구성하여 현재 바이러스의 시간과 번호를 차례로 넣어주면, 바이러스 중에서 시간이 가장 적은 바이러스가 먼저 선택되고, 같은 시간 내에서는 낮은 번호부터 선택된다. 풀이 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/2828 2828번: 사과 담기 게임 상근이는 오락실에서 바구니를 옮기는 오래된 게임을 한다. 스크린은 N칸으로 나누어져 있다. 스크린의 아래쪽에는 M칸을 차지하는 바구니가 있다. (M[0,4,-2](dislist) 4.오른쪽으로 움직이는경우 packlist의 끝에있는 값이 spacelist에있는 값까지 도달할 수 있도록 움직인다 예)바구니가 1에서 5로 움직이는 경우 [1,2]->[2,3]->[3,4]->[4,5] 3번움직임 5.왼쪽으로 움직이는경우 packlist의 처음에있는 값이 spacelist에있는 값까지 도달할 수 있도록 움직인다 예)바구니가 5에서 3으로 움직이는경우 [4,5]->[3,4] 1번 움직임
![]()
문제 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..
