기본으로 다시 돌아가기
코테 유형 한번 더 훑고 시작
1. 그리디(탐욕법)
#파이썬
n = 1260
count = 0
#큰 단위의 화폐부터 차례대로 확인
coin_types = [500, 100, 50, 10]
for coin in coin_types:
count += n // coin #해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
n %= coin # 나누기 연산 후 몫이 아닌 나머지를 구함
print(count)#자바
public class Main {
public static void main(String[] args) {
int n = 1260;
int cnt = 0;
int[] coinTypes = {500, 100, 50, 10};
for (int i = 0; i < 4; i++) {
int coin = coinTypes[i];
cnt += n / coin;
n %= coin;
}
System.out.println(cnt);
}
}- 큰 수의 법칙
#파이썬
n, m, k = map(int, input().split())
data = list(map(int, input().split())
data.sort()
first = data[n-1]
second = data[n-2]
result = 0
while True:
for i in range(k):
if m == 0:
break
result += first
m -= 1
if m == 0:
break
result += second
m -= 1
print(result)#자바
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// N, M, K를 공백을 기준으로 구분하여 입력 받기
int n = sc.nextInt();
int m = sc.nextInt();
int k = sc.nextInt();
// N개의 수를 공백을 기준으로 구분하여 입력 받기
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
Arrays.sort(arr); // 입력 받은 수들 정렬하기
int first = arr[n - 1]; // 가장 큰 수
int second = arr[n - 2]; // 두 번째로 큰 수
// 가장 큰 수가 더해지는 횟수 계산
int cnt = (m / (k + 1)) * k;
cnt += m % (k + 1);
int result = 0;
result += cnt * first; // 가장 큰 수 더하기
result += (m - cnt) * second; // 두 번째로 큰 수 더하기
System.out.println(result);
}
}- 숫자 카드 게임
#파이썬
n, m = map(int, input().split())
result = 0
for i in range(n):
data = list(map(int, input().split()))
min_value = min(data)
result = max(result, min_value)
print(result)
# 2중 반복문 구조를 이용한 답안
n, m = map(int, input().split())
result = 0
for i in range(n):
data = list(map(int, input().split()))
min_value = 10001
for a in data:
min_value = min(min_value, a)
result = max(result, min_value)
print(result)#자바
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// N, M, K를 공백을 기준으로 구분하여 입력 받기
int n = sc.nextInt();
int m = sc.nextInt();
int k = sc.nextInt();
// N개의 수를 공백을 기준으로 구분하여 입력 받기
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
Arrays.sort(arr); // 입력 받은 수들 정렬하기
int first = arr[n - 1]; // 가장 큰 수
int second = arr[n - 2]; // 두 번째로 큰 수
// 가장 큰 수가 더해지는 횟수 계산
int cnt = (m / (k + 1)) * k;
cnt += m % (k + 1);
int result = 0;
result += cnt * first; // 가장 큰 수 더하기
result += (m - cnt) * second; // 두 번째로 큰 수 더하기
System.out.println(result);
}
}- 1이 될 때까지
#파이썬 1번 방식
n, k = map(int, input().split())
result = 0
while n >= k:
while n % k != 0:
n -= 1
result += 1
n //= k # 최대한 많이 나누기
result += 1
while n > 1:
n -= 1
result += 1
print(result)
#파이썬 2번 방식
n, k = map(int, input().split())
result = 0
while True:
target = (n//k)*k
result += (n-target)
n = target
if n<k:
break
result += 1
n //= k
result += (n-1)
print(result)#자바풀이
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// N, K를 공백을 기준으로 구분하여 입력 받기
int n = sc.nextInt();
int k = sc.nextInt();
int result = 0;
while (true) {
// N이 K로 나누어 떨어지는 수가 될 때까지만 1씩 빼기
int target = (n / k) * k;
result += (n - target);
n = target;
// N이 K보다 작을 때 (더 이상 나눌 수 없을 때) 반복문 탈출
if (n < k) break;
// K로 나누기
result += 1;
n /= k;
}
// 마지막으로 남은 수에 대하여 1씩 빼기
result += (n - 1);
System.out.println(result);
}
}2. 구현
(1) 상하좌우
- 시뮬레이션 유형 : 일련의 명령에 따라 개체를 차례대로 이동시킨다는 점
n = int(input())
x, y = 1, 1
plans=input().split()
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
move_types = ['L', 'R', 'U', 'D']
for plan in plans:
for i in range(len(move_types)):
if plan == move_types[i]:
nx = x + dx[i]
ny = y + dy[i]
if nx<1 or ny<1 or nx>n or ny>n:
continue
x, y = nx, ny
print(x, y)import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// N을 입력받기
int n = sc.nextInt();
sc.nextLine(); // 버퍼 비우기
String[] plans = sc.nextLine().split(" ");
int x = 1, y = 1;
// L, R, U, D에 따른 이동 방향
int[] dx = {0, 0, -1, 1};
int[] dy = {-1, 1, 0, 0};
char[] moveTypes = {'L', 'R', 'U', 'D'};
// 이동 계획을 하나씩 확인
for (int i = 0; i < plans.length; i++) {
char plan = plans[i].charAt(0);
// 이동 후 좌표 구하기
int nx = -1, ny = -1;
for (int j = 0; j < 4; j++) {
if (plan == moveTypes[j]) {
nx = x + dx[j];
ny = y + dy[j];
}
}
// 공간을 벗어나는 경우 무시
if (nx < 1 || ny < 1 || nx > n || ny > n) continue;
// 이동 수행
x = nx;
y = ny;
}
System.out.println(x + " " + y);
}
}(2) 시각
- 완전탐색 : 가능한 경우의 수를 모두 검사해보는 탐색방법
h = int(input())
count = 0
for i in range(h+1):
for j in range(60):
for k in range(60):
if '3' in str(i) + str(j) + str(k):
count += 1
print(count)import java.util.*;
public class Main {
// 특정한 시각 안에 '3'이 포함되어 있는지의 여부
public static boolean check(int h, int m, int s) {
if (h % 10 == 3 || m / 10 == 3 || m % 10 == 3 || s / 10 == 3 || s % 10 == 3)
return true;
return false;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// H를 입력받기
int h = sc.nextInt();
int cnt = 0;
for (int i = 0; i <= h; i++) {
for (int j = 0; j < 60; j++) {
for (int k = 0; k < 60; k++) {
// 매 시각 안에 '3'이 포함되어 있다면 카운트 증가
if (check(i, j, k)) cnt++;
}
}
}
System.out.println(cnt);
}
}(3) 왕실의 나이트
- 시뮬레이션 유형
input_data = input()
row = int(input_data[1])
column = int(ord(input_data[0]))-int(ord('a'))+1
steps = [(-2, -1), (-1, -2) (1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1)]
result = 0
for step in steps:
next_row = row + step[0]
next_column = column + step[1]
if next_row >= 1 and next_row <= 8 and next_column >= 1 and next_column <= 8:
result += 1
print(result)import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 현재 나이트의 위치 입력받기
String inputData = sc.nextLine();
int row = inputData.charAt(1) - '0';
int column = inputData.charAt(0) - 'a' + 1;
// 나이트가 이동할 수 있는 8가지 방향 정의
int[] dx = {-2, -1, 1, 2, 2, 1, -1, -2};
int[] dy = {-1, -2, -2, -1, 1, 2, 2, 1};
// 8가지 방향에 대하여 각 위치로 이동이 가능한지 확인
int result = 0;
for (int i = 0; i < 8; i++) {
// 이동하고자 하는 위치 확인
int nextRow = row + dx[i];
int nextColumn = column + dy[i];
// 해당 위치로 이동이 가능하다면 카운트 증가
if (nextRow >= 1 && nextRow <= 8 && nextColumn >= 1 && nextColumn <= 8) {
result += 1;
}
}
System.out.println(result);
}
}(4) 게임 개발
- 시뮬레이션 유형
n, m = map(int, input().split())
d = [[0] * m for _ in range(n)]
x, y, direction = map(int, input().split())
d[x][y] = 1
array = []
for i in range(n):
array.append(list(map(int, input().split())))
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
def turn_left():
global direction
direction -= 1
if direction == -1:
direciton = 3
#시뮬레이션 시작
count = 1
turn_time = 0
while True:
#왼쪽으로 회전
turn_left()
nx = x + dx[direction]
ny = y + dy[direction]
# 회전한 이후 정면에 가보지 않은 칸이 존재하는 경우 이동
if d[nx][ny] == 0 and array[nx][ny] == 0:
d[nx][ny] = 1
x = nx
y = ny
count += 1
turn_time = 0
continue
# 회전한 이후 정면에 가보지 않은 칸이 없거나 바다인 경우
else:
turn_time += 1
# 네 방향 모두 갈 수 없는 경우
if turn_time == 4
nx = x - dx[direction]
ny = y - dy[direction]
# 뒤로 갈 수 있다면 이동하기
if array[nx][ny] == 0:
x = nx
y = ny
#뒤가 바다로 막혀있는 경우
else:
break
turn_time = 0
print(count)import java.util.*;
public class Main {
public static int n, m, x, y, direction;
// 방문한 위치를 저장하기 위한 맵을 생성하여 0으로 초기화
public static int[][] d = new int[50][50];
// 전체 맵 정보
public static int[][] arr = new int [50][50];
// 북, 동, 남, 서 방향 정의
public static int dx[] = {-1, 0, 1, 0};
public static int dy[] = {0, 1, 0, -1};
// 왼쪽으로 회전
public static void turn_left() {
direction -= 1;
if (direction == -1) direction = 3;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// N, M을 공백을 기준으로 구분하여 입력받기
n = sc.nextInt();
m = sc.nextInt();
// 현재 캐릭터의 X 좌표, Y 좌표, 방향을 입력받기
x = sc.nextInt();
y = sc.nextInt();
direction = sc.nextInt();
d[x][y] = 1; // 현재 좌표 방문 처리
// 전체 맵 정보를 입력 받기
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
arr[i][j] = sc.nextInt();
}
}
// 시뮬레이션 시작
int cnt = 1;
int turn_time = 0;
while (true) {
// 왼쪽으로 회전
turn_left();
int nx = x + dx[direction];
int ny = y + dy[direction];
// 회전한 이후 정면에 가보지 않은 칸이 존재하는 경우 이동
if (d[nx][ny] == 0 && arr[nx][ny] == 0) {
d[nx][ny] = 1;
x = nx;
y = ny;
cnt += 1;
turn_time = 0;
continue;
}
// 회전한 이후 정면에 가보지 않은 칸이 없거나 바다인 경우
else turn_time += 1;
// 네 방향 모두 갈 수 없는 경우
if (turn_time == 4) {
nx = x - dx[direction];
ny = y - dy[direction];
// 뒤로 갈 수 있다면 이동하기
if (arr[nx][ny] == 0) {
x = nx;
y = ny;
}
// 뒤가 바다로 막혀있는 경우
else break;
turn_time = 0;
}
}
System.out.println(cnt);
}
}3. DFS/BFS
(1) 음료수 얼려먹기 - DFS
n, m = map(int, input().split())
graph = []
for i in range(n):
graph.append(list(map(int, input())))
def dfs(x, y):
if x<=1 or x>=n or y<=1 or y>=m:
return False
if graph[x][y] == 0:
graph[x][y] = 1
dfs(x-1, y)
dfs(x, y-1)
dfs(x+1, y)
dfs(x, y+1)
return True
return False
result = 0
for i in range(n):
for j in range(m):
if dfs(i, j) == True:
result += 1
print(result) import java.util.*;
public class Main {
public static int n, m;
public static int[][] graph = new int[1000][1000];
// DFS로 특정 노드를 방문하고 연결된 모든 노드들도 방문
public static boolean dfs(int x, int y) {
// 주어진 범위를 벗어나는 경우에는 즉시 종료
if (x <= -1 || x >=n || y <= -1 || y >= m) {
return false;
}
// 현재 노드를 아직 방문하지 않았다면
if (graph[x][y] == 0) {
// 해당 노드 방문 처리
graph[x][y] = 1;
// 상, 하, 좌, 우의 위치들도 모두 재귀적으로 호출
dfs(x - 1, y);
dfs(x, y - 1);
dfs(x + 1, y);
dfs(x, y + 1);
return true;
}
return false;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// N, M을 공백을 기준으로 구분하여 입력 받기
n = sc.nextInt();
m = sc.nextInt();
sc.nextLine(); // 버퍼 지우기
// 2차원 리스트의 맵 정보 입력 받기
for (int i = 0; i < n; i++) {
String str = sc.nextLine();
for (int j = 0; j < m; j++) {
graph[i][j] = str.charAt(j) - '0';
}
}
// 모든 노드(위치)에 대하여 음료수 채우기
int result = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// 현재 위치에서 DFS 수행
if (dfs(i, j)) {
result += 1;
}
}
}
System.out.println(result); // 정답 출력
}
}(2) 미로 탈출 - BFS
from collections import deque
n, m = map(int, input().split())
graph = []
for i in range(n):
graph.append(list(map(int, input())))
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs(x, y):
queue = deque()
queue.append((x, y))
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = x + dy[i]
if nx<0 or ny<0 or nx>=n or ny>=m:
continue
#벽인 경우 무시
if graph[nx][ny] == 0:
continue
#해당 노드를 처음 방문하는 경우에만 최단 거리 기록
if graph[nx][ny] == 1:
graph[nx][ny] = graph[x][y] + 1
queue.append((nx, ny))
return graph[n -1][m - 1]
print(bfs(0, 0))import java.util.*;
class Node {
private int x;
private int y;
public Node(int x, int y) {
this.x = x;
this.y = y;
}
public int getX() {
return this.x;
}
public int getY() {
return this.y;
}
}
public class Main {
public static int n, m;
public static int[][] graph = new int[201][201];
// 이동할 네 가지 방향 정의 (상, 하, 좌, 우)
public static int dx[] = {-1, 1, 0, 0};
public static int dy[] = {0, 0, -1, 1};
public static int bfs(int x, int y) {
// 큐(Queue) 구현을 위해 queue 라이브러리 사용
Queue<Node> q = new LinkedList<>();
q.offer(new Node(x, y));
// 큐가 빌 때까지 반복하기
while(!q.isEmpty()) {
Node node = q.poll();
x = node.getX();
y = node.getY();
// 현재 위치에서 4가지 방향으로의 위치 확인
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
// 미로 찾기 공간을 벗어난 경우 무시
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
// 벽인 경우 무시
if (graph[nx][ny] == 0) continue;
// 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
if (graph[nx][ny] == 1) {
graph[nx][ny] = graph[x][y] + 1;
q.offer(new Node(nx, ny));
}
}
}
// 가장 오른쪽 아래까지의 최단 거리 반환
return graph[n - 1][m - 1];
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// N, M을 공백을 기준으로 구분하여 입력 받기
n = sc.nextInt();
m = sc.nextInt();
sc.nextLine(); // 버퍼 지우기
// 2차원 리스트의 맵 정보 입력 받기
for (int i = 0; i < n; i++) {
String str = sc.nextLine();
for (int j = 0; j < m; j++) {
graph[i][j] = str.charAt(j) - '0';
}
}
// BFS를 수행한 결과 출력
System.out.println(bfs(0, 0));
}
}4. 정렬
1) 선택정렬
for i in range(len(array):
min_index = i
for j in range(i + 1, len(array)):
if array[min_index] > array[j]:
min_index = j
array[i], array[min_index] = array[min_index], array[i]2) 삽입정렬
for i in range(1, len(array)):
for j in range(i, -, -1):
if array[j] < array[j-1]:
array[j], array[j-1] = array[j-1], array[j]
else:
break
print(array)(1) 위에서 아래로
n = int(input())
array=[]
for i in range(n):
array.append(int(input()))
array = sorted(array, reverse=True)
for i in array:
print(i, end = '')import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// N을 입력받기
int n = sc.nextInt();
// N개의 정수를 입력받아 리스트에 저장
Integer[] arr = new Integer[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
// 기본 정렬 라이브러리를 이용하여 내림차순 정렬 수행
Arrays.sort(arr, Collections.reverseOrder());
for(int i = 0; i < n; i++) {
System.out.print(arr[i] + " ");
}
}
}(2) 성적이 낮은 순서로 학생 출력하기
n = int(input())
array = []
for i in range(n):
input_data = input().split()
array.append((input_data[0], int(input_data[1])))
array = sorted(array, key = lambda student: student[1])
for student in array:
print(student[0], end='')import java.util.*;
class Student implements Comparable<Student> {
private String name;
private int score;
public Student(String name, int score) {
this.name = name;
this.score = score;
}
public String getName() {
return this.name;
}
public int getScore() {
return this.score;
}
// 정렬 기준은 '점수가 낮은 순서'
@Override
public int compareTo(Student other) {
if (this.score < other.score) {
return -1;
}
return 1;
}
}
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// N을 입력받기
int n = sc.nextInt();
// N명의 학생 정보를 입력받아 리스트에 저장
List<Student> students = new ArrayList<>();
for (int i = 0; i < n; i++) {
String name = sc.next();
int score = sc.nextInt();
students.add(new Student(name, score));
}
Collections.sort(students);
for (int i = 0; i < students.size(); i++) {
System.out.print(students.get(i).getName() + " ");
}
}
}(3) 두 배열의 원소 교체
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a.sort()
b.sort(reverse=True)
for i in range(k):
if a[i] < b[i]:
a[i], b[i] = b[i], a[i]
else:
break
print(sum(a))import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// N과 K를 입력받기
int n = sc.nextInt();
int k = sc.nextInt();
// 배열 A의 모든 원소를 입력받기
Integer[] a = new Integer[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
// 배열 B의 모든 원소를 입력받기
Integer[] b = new Integer[n];
for (int i = 0; i < n; i++) {
b[i] = sc.nextInt();
}
// 배열 A는 오름차순 정렬 수행
Arrays.sort(a);
// 배열 B는 내림차순 정렬 수행
Arrays.sort(b, Collections.reverseOrder());
// 첫 번째 인덱스부터 확인하며, 두 배열의 원소를 최대 K번 비교
for (int i = 0; i < k; i++) {
// A의 원소가 B의 원소보다 작은 경우
if (a[i] < b[i]) {
// 두 원소를 교체
int temp = a[i];
a[i] = b[i];
b[i] = temp;
}
// A의 원소가 B의 원소보다 크거나 같을 때, 반복문을 탈출
else break;
}
// 배열 A의 모든 원소의 합을 출력
long result = 0;
for (int i = 0; i < n; i++) {
result += a[i];
}
System.out.println(result);
}
}5. 이진탐색
(1) 부품찾기
def binary_search(array, target, start, end):
while start <= end:
mid = (start+end) // 2
if array[mid] == target:
return mid
elif array[mid] > target:
end = mid -1
else:
start = mid + 1
return None
n = int(input())
array = list(map(int, input().split()))
array.sort()
m = int(input())
x = list(map(int, input().split()))
for i in x:
result = binary_search(array, i, 0, n-1)
if result != None:
print('yes', end=' ')
else:
print('no', end= ' ') import java.util.*;
public class Main {
// 이진 탐색 소스코드 구현(반복문)
public static int binarySearch(int[] arr, int target, int start, int end) {
while (start <= end) {
int mid = (start + end) / 2;
// 찾은 경우 중간점 인덱스 반환
if (arr[mid] == target) return mid;
// 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
else if (arr[mid] > target) end = mid - 1;
// 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
else start = mid + 1;
}
return -1;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// N(가게의 부품 개수)
int n = sc.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
// 이진 탐색을 수행하기 위해 사전에 정렬 수행
Arrays.sort(arr);
// M(손님이 확인 요청한 부품 개수)
int m = sc.nextInt();
int[] targets = new int[m];
for (int i = 0; i < m; i++) {
targets[i] = sc.nextInt();
}
// 손님이 확인 요청한 부품 번호를 하나씩 확인
for (int i = 0; i < m; i++) {
// 해당 부품이 존재하는지 확인
int result = binarySearch(arr, targets[i], 0, n - 1);
if (result != -1) {
System.out.print("yes ");
}
else {
System.out.print("no ");
}
}
}
}
Footer(2) 떡볶이 떡 만들기
n, m = list(map(int, input().split(' ')))
array = list(map(int, input().split()))
start = 0
end = max(array)
result = 0
while(start <= end):
total = 0
mid = (start+end) // 2
for x in array:
if x > mid:
total += x - mid
if total < m:
end = mid -1
else:
result = mid
start = mid + 1
print(result)import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 떡의 개수(N)와 요청한 떡의 길이(M)
int n = sc.nextInt();
int m = sc.nextInt();
// 각 떡의 개별 높이 정보
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
// 이진 탐색을 위한 시작점과 끝점 설정
int start = 0;
int end = (int) 1e9;
// 이진 탐색 수행 (반복적)
int result = 0;
while (start <= end) {
long total = 0;
int mid = (start + end) / 2;
for (int i = 0; i < n; i++) {
// 잘랐을 때의 떡의 양 계산
if (arr[i] > mid) total += arr[i] - mid;
}
if (total < m) { // 떡의 양이 부족한 경우 더 많이 자르기(왼쪽 부분 탐색)
end = mid - 1;
}
else { // 떡의 양이 충분한 경우 덜 자르기(오른쪽 부분 탐색)
result = mid; // 최대한 덜 잘랐을 때가 정답이므로, 여기에서 result에 기록
start = mid + 1;
}
}
System.out.println(result);
}
}6. 다이나믹 프로그래밍(DP)
- 탑다운 방식 : 큰 문제를 해결하기 위해 작은 문제를 호출
(재귀함수를 이용한 다이나믹 프로그래밍 방법) / 하향식 / 메모이제이션 방식 - 보텀업 방식 :작은 문제부터 차근차근 답을 도출 (단순 반복문을 이용하여 소스코드 작성) / 상향식
(1) 1로 만들기
x = int(input())
d = [0]*30001
for i in range(2, x+1):
d[i] = d[i-1] + 1
if i % 2 == 0:
d[i] = min(d[i], d[i // 2] + 1)
if i % 3 == 0:
d[i] = min(d[i], d[i // 3] + 1)
if i % 5 == 0:
d[i] = min(d[i], d[i // 5] + 1)
print(d[x])import java.util.*;
public class Main {
// 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
public static int[] d = new int[30001];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int x = sc.nextInt();
// 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
for (int i = 2; i <= x; i++) {
// 현재의 수에서 1을 빼는 경우
d[i] = d[i - 1] + 1;
// 현재의 수가 2로 나누어 떨어지는 경우
if (i % 2 == 0)
d[i] = Math.min(d[i], d[i / 2] + 1);
// 현재의 수가 3으로 나누어 떨어지는 경우
if (i % 3 == 0)
d[i] = Math.min(d[i], d[i / 3] + 1);
// 현재의 수가 5로 나누어 떨어지는 경우
if (i % 5 == 0)
d[i] = Math.min(d[i], d[i / 5] + 1);
}
System.out.println(d[x]);
}
}(2) 개미전사
n = int(input())
array = list(map(int, input().split()))
d = [0] * 100
d[0] = array[0]
d[1] = max(array[0], array[1])
for i in range(2, n):
d[i] = max(d[i-1], d[i-2] + array[i])
print(d[n-1])import java.util.*;
public class Main {
// 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
public static int[] d = new int[100];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 정수 N을 입력받기
int n = sc.nextInt();
// 모든 식량 정보 입력받기
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
// 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
d[0] = arr[0];
d[1] = Math.max(arr[0], arr[1]);
for (int i = 2; i < n; i++) {
d[i] = Math.max(d[i - 1], d[i - 2] + arr[i]);
}
// 계산된 결과 출력
System.out.println(d[n - 1]);
}
}(3) 바닥공사
n = int(input())
d = [0] * 1001
d[1] = 1
d[2] = 3
for i in range(3, n + 1):
d[i] = d[i - 1] + 2 * d[i - 2] % 796796import java.util.*;
public class Main {
// 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
public static int[] d = new int[1001];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 정수 N을 입력받기
int n = sc.nextInt();
// 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
d[1] = 1;
d[2] = 3;
for (int i = 3; i <= n; i++) {
d[i] = (d[i - 1] + 2 * d[i - 2]) % 796796;
}
// 계산된 결과 출력
System.out.println(d[n]);
}
}(4) 효율적인 화폐 구성
n, m = map(int, input().split())
array = []
for i in range(n):
array.append(int(input())
d = [10001] * (m + 1)
d[0] = 0
for i in range(n):
for j in range(array[i], m+1):
if d[j - array[i]] != 10001:
d[j] = min(d[j], d[j - array[i]] + 1)
if d[m] == 10001:
print(-1)
else:
print(d[m])import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 정수 N, M을 입력받기
int n = sc.nextInt();
int m = sc.nextInt();
// N개의 화폐 단위 정보를 입력 받기
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
// 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
int[] d = new int[m + 1];
Arrays.fill(d, 10001);
// 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
d[0] = 0;
for (int i = 0; i < n; i++) {
for (int j = arr[i]; j <= m; j++) {
// (i - k)원을 만드는 방법이 존재하는 경우
if (d[j - arr[i]] != 10001) {
d[j] = Math.min(d[j], d[j - arr[i]] + 1);
}
}
}
// 계산된 결과 출력
if (d[m] == 10001) { // 최종적으로 M원을 만드는 방법이 없는 경우
System.out.println(-1);
}
else {
System.out.println(d[m]);
}
}
}
This is a velog that freely records the process I learn.