자바

[Java] 백준 #1463 1로 만들기

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 정수 X에 사용할 수 있는 연산 세 가지를 적절히 사용해서 정수 N을 1로 만든다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 연산 사용 횟수의 최솟값 구하기 💡 알고리즘 다이나믹 프로그래밍 💡 접근 RGB거리처럼 모든 케이스의 계산횟수가 동일한 문제가 아니므로, 배열만으로는 해결하기 어려울 것 같다. → 재귀함수를 작성하고, 전역변수를 통해 최솟값을 관리하자. 💡 코드 package DP; import java.io.BufferedReader; imp..

[Java] 백준 #10825 국영수

https://www.acmicpc.net/problem/10825 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net 학생 N명의 국, 영, 수 점수 학생 성적 정렬하기 국어 점수 감소하는 순서 국어 점수 같으면 → 영어 점수 증가 국어, 영어 같으면 → 수학 점수 감소 모두 같으면 이름 사전순 증가 (모든 대문자는 소문자 앞에) 아스키 코드에서 대문자는 소문자보다 작으므로 사전순으로 앞에 온다. 💡 알고리즘 정렬 💡 접근 객체를 정렬하는 기준을 만들기 위해 자바에서 제공하는 Comparat..

[Java] 백준 #1158 요세푸스 문제

https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 1번부터 N번까지 N명의 사람이 원을 이루며 앉아있음 양의정수 K → 순서대로 K번째 사람 제거 → N명이 제거될 때까지 (N, K) 요세푸스 순열 구하기 💡 알고리즘 자료구조, 큐 💡 접근 처음에 중간에 원소가 나가면 인덱스도 하나씩 줄어들어야 하겠구나 라는 잘못된 생각을 해서 큐를 생각해내지 못했다. (규칙만 추가하며 산으로 가던 코드) int idx = K - 1; LinkedList res = new LinkedList(); while(list.size() > 0){ res.add..

[Java] 백준 #1780 종이의 개수

https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net N x N 행렬 종이 → 각각 -1, 0, 1 중 하나 저장 규칙에 따라 적절한 크기로 종이 자르기 종이가 모두 같은 수 → 그대로 사용 모두 같은 수 x → 같은 크기의 종이 9개로 자르고 각각의 잘린 종이에 대하여 1번 과정 반복 이와같이 종이를 잘랐을 때 -1, 0, 1로만 채워진 종이의 개수 각각 구하기 N은 3^k꼴, 1 ≤ N ≤ 3^7 💡 알고리즘 분할 정복, 재귀 💡 접근..