![]()
문제 링크 https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 접근 방법 이 문제를 완전 탐색으로 풀려고 한다면 모든 칸을 접근하며 정사각형 형태인지를 판별해야할 것 입니다. 정사각형 형태인지 판별하는 것은 쉽지만 정사각형의 길이가 1 ~ min(n, m)인 경우까지 확인해보아야 하므로 정확한 계산은 어렵지만 못해도 n * m * min(n, m)의 수행 시간을 가질 것이라고 생각되고 이는 최악의 경우에 1초를 넘길 것입니다. 따라서 이전의 정사각형 크기를 기록하여(dp 배열을 이용한 메모이제이션) 현재 위치에서의 최..
문제 https://www.acmicpc.net/problem/14728 Algorithm 전형적인 배낭 문제이다. dp[i][j] : i번째 단원까지 고려했을 때, 총 공부 시간이 j일때 얻을 수 있는 최대 점수 점화식 : dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i].first] + v[i].second - dp[i - 1][j]는 i번째 단원을 선택하지 않는 경우, i번째 단원을 고려하지 않고 이전 단원까지의 최대 점수 - dp[i - 1][j - v[i].first] + v[i].second는 i번째 단원을 공부하기 위해 필요한 시간 v[i].first가 j보다 작거나 같은 경우에만 가능하다. 선택하는 경우에는 해당 단원을 선택하기 전까지의 최대 점수에 현재..
![]()
https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제 분석 문제 설명 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 소스코드 import java.io.BufferedReader; im..
![]()
https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net dp(동적 계획법 - Dynamic Programming)인 문제이다. 처음에 봤을 때는 그리디가 생각이 났지만, 현재 기준으로 높은 숫자가 아닌, 합 중 최대값을 출력해야되므로 dp를 이용하여 풀어야 된다. 양 끝에 있는 숫자들은 더할 수 있는 값들이 정해져있으므로, 제일 왼쪽과 제일 오른쪽의 숫자들은 이전 값들과 누적된 합들을 합해준다. 그리고 중간에 있는 값들은 dp 내에 있는 현재 idx와 이전 idx 값 중 비교하여 큰 값을 불러와서 출력하도록 한다. 그 부분..
문제 https://www.acmicpc.net/problem/14430 14430번: 자원 캐기 인류의 차세대 인공지능 자원 캐기 로봇인 WOOK은 인간 대신 자원을 캐는 로봇이다. WOOK은 언제나 제한된 범위 내에서 자원을 탐색하며, 왼쪽 위 (1, 1)부터 오른쪽 아래 (N, M)까지 자원을 탐색한다. www.acmicpc.net Algorithm 인공지능 WOOK은 오른쪽(r, c+1)과 왼쪽(r+1, c) 방향으로만 움직일 수 있다. 따라서, 현재 위치와 이전에 기록해둔 최댓값을 이용한다. 즉, DP의 Memoization을 활용하여 풀이한다.주의할 점은 인덱싱이다. 가장 윗줄과 왼쪽줄은 먼저 채워주고, 1부터 n까지 기록하도록 한다. Code n,m=map(int,input().split()..
https://www.acmicpc.net/problem/8979 8979번: 올림픽 입력의 첫 줄은 국가의 수 N(1 ≤ N ≤ 1,000)과 등수를 알고 싶은 국가 K(1 ≤ K ≤ N)가 빈칸을 사이에 두고 주어진다. 각 국가는 1부터 N 사이의 정수로 표현된다. 이후 N개의 각 줄에는 차례대로 각 www.acmicpc.net 문제 국가의 수 N(1 n >> k; for (int i = 0; i > a >> b >> c >> d; v.push_back({ {b,c},{d,a} }); } sort(v.rbegin(), v.rend()); for (int i = 0; i < v.size(); i++) { if (v[i].second.second == k) break; if..
![]()
https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제 코드 from functools import reduce def in_cache(func): # decorator를 사용 - 메모이제이션 cache = {} def wrapper(n): if n in cache: return cache[n] else: cache[n] = func(n) return cache[n] return wrapper @in_cache def factorial_reduce(n): # redu..
![]()
https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 문제 풀이 동전의 사용하는 개수의 최소를 구해야 하기 때문에 처음에는 list를 만들고 동전의 종류를 넣은후 큰것 부터 작은것 순으로 비교하여 동전이 금액의 크기보다 작으면 동전 사용 개수의 변수 c와 금액의 변수 m에 각각 c+=금액//동전 을 해주고 m=m%동전을 해준다 코드
![]()
문제 링크 https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 문제 풀이 상근이가 왼쪽부터 숫자들을 더하거나 빼나가며 최우항의 숫자를 만드는 경우의 수를 출력하는 문제이다. 완전 탐색을 사용하면 단순하게 생각하였을 때 O(2^n)의 시간복잡도를 가지기 때문에 패턴을 찾아 문제를 풀어야 한다. 문제 설명 중 "상근이는 아직 학교에서 음수를 배우지 않았고, 20을 넘는 수는 모른다. 따라서, 왼쪽부터 계산할 때, 중간에 나오는 수가 모두 0 이..
문제 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 코드 #include #include #include using namespace std; /* 계단 오르기(2579) 계단 아래 시작점부터 계단 꼭대기에 위치한 도착지까지 가야함 각각의 계단에는 일정한 점수가 쓰여 있음. 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 됨 계단을 오르는 규칙 1. 계단은 한번에 1 혹은 2 계단 씩 오를 수 있음 2. 연속된 세개의 계단을 모두 밟아소는 안됨 3. 마지..
https://www.acmicpc.net/problem/2890 2890번: 카약 첫째 줄에 R과 C가 주어진다. 다음 R개 줄에는 '.', 'S', 'F', '1'~'9'로 이루어진 위성 지도가 주어진다. 한 줄에는 최대 한 개의 카약만 있고, 위성 사진에 있는 카약은 항상 9개이다. (10 ≤ R, C ≤ 50) www.acmicpc.net 코드 #include #include #include #include #include #include #include #include #include #include #include #include #include #define LL long long using namespace std; int arr[10]; int ord[10]; int ans[10]; in..
문제 https://www.acmicpc.net/problem/1965 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 www.acmicpc.net 코드 import sys def calc(box): n = len(box) dp = [1] * n for i in range(1, n): for j in range(i): if box[i] > box[j]: dp[i] = max(dp[i], dp[j] + 1) return max(dp) n=int(input()) box=list(map(int,sys.stdin.readline().rstrip().sp..
