1051번: 숫자 정사각형 (acmicpc.net) 1051번: 숫자 정사각형 N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 www.acmicpc.net 문제이해 해당 문제는 N * M 크기의 직사각형에서 각 꼭지점이 같은 정사각 형을 구하는 문제이다. 풀이 정사각형의 최대 크기는 직사각형중 작은 부분일 것이다. 이점을 고려해 가장 큰 정사각형 부터 가장 작은 정사각형을 반복해 꼭지점이 같은 지 비교하고 꼭지점이 모두 같다면 해당 정사각형을 출력하면 된다. import java.io.*; import java.util.*; public class Main { s..
1699번: 제곱수의 합 (acmicpc.net) 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 문제이해 해당 문제는 식을 이용해 풀 면 될 것이라고 생각은 했지만 해당 식을 찾지 못했고 검색을 통해 문제를 이해 및 핵려 할 수 있었다. [백준] 1699번 제곱수의 합 - Java, 자바 (velog.io) [백준] 1699번 제곱수의 합 - Java, 자바 실버 3 https://www.acmicpc.net/problem/1699테이블 정의하기dpi = 제곱수 합의 ..
1654번: 랜선 자르기 (acmicpc.net) 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 문제이해 이전에 풀었던 통나무 수를 구하는 문제와 비슷하다 단 해당 문제의 경우 이진 탐색을 하지 않을 경우 시간 초과 오류가 난다. 해당 문제를 고려해서 풀면된다. 풀이 코드는 별거 없다. 최대 길이를 구하고 최대 길이와 최소길이 1의 중간 값을 기준으로 비교를 해나간다. 비교가 모두 끝나면 가장 큰 값이 선택 되었을 것이고 그 값을 출력하면 문제는 해결된다. import java...
1564번: 팩토리얼5 (acmicpc.net) 1564번: 팩토리얼5 첫째 줄에 정수 N이 주어진다. N은 1,000,000보다 작거나 같다. 또, 9보다 크거나 같다. www.acmicpc.net 문제이해 해당 문제는 팩토리얼을 구한뒤 0이 아닌 마지막 5자리를 구하는 문제이다. 해당 문제의 경우 단순히 팩토리얼을 구해서 계산을 하면 너무 계산 시간이 오래 걸린다. 따라서 낮은 자리수들만으로 곱셈계산을 하는 식을 문제를 풀어야한다. 풀이 팩토리얼을 구하되 계산된 값을 적당히 작은 수로 나누어 주면서 낮은 단위의 수들만으로 계산을 진행한다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader..
import java.util.Scanner; public class text_22 { public static void main(String[] args) { Scanner in = new Scanner(System.in); int sum = Integer.MAX_VALUE; //가장 작은 수를 찾아야 하기에 기본값 String[] subtraction = in.nextLine().split("-");//-를 기준으로 나눈다. for(int i = 0; i < subtraction.length; i++) { int temp = 0; // 뺄셈으로 나뉜 토큰 중에 덧셈들을 추가한다. String[] addition = subtraction[i].split("\\+"); // 덧셈으로 나뉜 토큰들을 모두 ..
1535번: 안녕 (acmicpc.net)[DP] [DP] 배낭 문제 (Knapsack Problem) DP의 대표적인 문제 velog.io 문제이해 이번문제는 hp가 0이 되기 전까지 기쁨을 최대로 많이 선택하는 문제로 배낭 문제와 완전히 일치한다. 참고: 배낭 문제 (Knapsack Problem) (velog.io) [DP] 배낭 문제 (Knapsack Problem) DP의 대표적인 문제 velog.io 풀이 우선 각체력의 최대값을 저장할 배열에 현재 hp를 빼고 happy를 선택했을 때와 선택을 안했을때의 최대 값을 비교하면된다. 이때 dp[99]를 선택하는 이유는 100을 선택하게 되면 죽은 거기 때문이다. import java.io.BufferedReader; import java.io.IO..
1503번: 세 수 고르기 (acmicpc.net) 1503번: 세 수 고르기 첫째 줄에 N(1 ≤ N ≤ 1,000)과 집합 S의 크기 M(0 ≤ M ≤ 50)이 주어진다. 둘째 줄에는 집합 S에 들어있는 수가 주어진다. 집합에 들어있는 수는 1,000보다 작거나 같은 자연수이고, 공백으로 구분되어 www.acmicpc.net 문제 이해 정해진 집합에 포함되어있지 않은 |N - xyz|를 구하는 문제이다. 해당 문제는 입력받은 수들을 모두 번갈아 가면서 확인하면 되는 간단한문제이다. 단 해당문제는 원소들의 수가 1000까지가 아니라 1001까지 허용해 줘야한다는 점만 명심하면 된다. 왜 1001까지 허용이 가능 하냐고 하면 우리는 가장 작은 수를 만드는 것을 명심해야한다. 1부터 무한대 까지의 자연수를..
1497번: 기타콘서트 (acmicpc.net) 1497번: 기타콘서트 첫째 줄에 기타의 개수 N과 곡의 개수 M이 주어진다. N은 10보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 기타의 이름과 기타가 연주할 수 있는 곡의 www.acmicpc.net 문제 이해 해당 문제는 최대 곡을 연주 할 수 있는 기타의 최소 수를 계산하는 문제이다. 처음 이 문제를 봤을땐 모든 곡을 연주 할 수 있는 최소의 기타수를 계산하는 문제로 이해해 문제를 풀었고 틀렸다. 이 문제는 모든 곡을 연주하는 것이 아닌 최대 곡을 연주하는 것을 명심해야한다. 풀이 기타수와 곡수를 입력받는다. 만약y이면 배열에 1 아니면 0을 담는다. 이때 모든 곡을 연주 하지 못 할 수 있기 때문에..
백준1406 (notion.so) 문제를 정리해둔 노션입니다.
백준1326 (notion.so) 문제를 정리해둔 노션입니다.
1455번: 뒤집기 II (acmicpc.net) 문제 이해 해당 문제는 동전을 뒤집는 문제이다. 하지만 해당 문제에서는 동전을 하나만 뒤집는게 아니라 현재 위치 까지의 직사각형 모양의 모든 동전을 뒤집어야한다. 풀이 입력을 받는다. 오른쪽 아래 동전부터 처음 동전까지 이동하면서 1인동전(뒤집어진 동전)을 모두 뒤집는다. 여기어 오른쪽 아래 부터 뒤집는 이유는 처음 부터 시작할 경우 진행하다보면 기존에 뒤집은 동전을 다시 뒤집어야 할 수 도 있기 때문이다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class ..