알고리즘/백준

문제 풀이 import java.util.Scanner; class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(), M = sc.nextInt(); int[][] map = new int[N][M]; for(int i = 0; i < N; i++) { for(int j = 0; j < M; j++) map[i][j] = sc.nextInt(); } int T = sc.nextInt(); while(T != 0) { int x1 = sc.nextInt(), y1 = sc.nextInt(), x2 = sc.nextInt(), y2 = sc.nextInt(), sum =..

문제 풀이 어떤 수의 십의 자리를 q, 일의 자리를 w이라고 할 때, q + w을 한 sum을 구한 뒤 x = w* 10 + sum % 10으로 초기화해 주며 x와 N이 같아질 때까지 반복하면 됩니다. q = 26 / 10 = 2, w = 26 % 10 = 6으로 구한뒤, 이 두 개를 합한 sum = 2 + 6 = 8 이 됩니다. 이제, x를 w * 10 + sum % 10한 값인 68로 새롭게 초기화를 해 줍니다. 다시, 68은 q = 6, w= 8로 쪼갤 수 있고, sum = 14 이므로, x = 8 * 10 + 14 % 10 = 80 + 4 = 84가 됩니다. 84는 q = 8, w = 4로 쪼갤 수 있고, sum = 12이므로, x = 4 * 10 + 12 % 10 = 42가 됩니다. 42는 q ..

문제 풀이 각자리 숫자의 갯수를 배열에 저장한뒤 Math.max를 이용해 최대값을 찾아낼껀데 6,9는 같이 쓰일 수 있으므로 두개의 수는 더해서 계산한다. 1~2는 1세트 3~4는 2세트므로 6,9의 자리수를 더한걸 2.0 double 값으로 나눈뒤 반올림하여 비교하여 최대값을 찾아낸다. 소스 import java.io.*; class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int value = Integer.parseInt(br.readLine()); int[] ints = new int[10..

문제 풀이 배열에 미리 월 별 일수를 초기회해둔다. 그리고 1월부터 x - 1 월까지 모든 월의 일수를 더하고 입력받은 y 더해 총 일수를 구합니다. 1월 1일이 월요일이므로 총 일수를 7로 나눈 나머지로 요일을 출력해줍니다. import java.io.*; import java.util.StringTokenizer; class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int month = Int..

문제 풀이 임의의 수열이 주어지고 이중 한 개 이상의 연속된 수를 선택해 큰 수를 만드는 문제이다. 메모리제이션을 이용하면 어렵지 않게 풀 수 있다. 일반적으로 제일 큰수를 만든다고 생각하면 -가 붙은 수를 제외하여 더하겠지만 예제 2같은 경우에 3,4,-4,6,5 가 되어 14라는 제일 큰수를 만들수있다. 이경우 -4가 앞에 3,4를 더한 값보다 작기때문에 -4까지 더한 값이 큰값이되는것이다. 즉, 큰수는 음수 양수 상관없이 연속으로 선택한 값중 제일 큰 값를 찾으면 되는 것이다. 즉, 메모이제이션은 이전까지 탐색했던 값과 현재 위치의 값을 비교하여 큰 값을 저장하면 되는 것이다. import java.io.*; import java.util.*; class Main { public static voi..

문제 풀이 부분수열은 자기자신의 값도 포함되기 때문에 최소 길이 값은 1로 초기화한다. 그리고 첫번째 값부터 반복문을 통해 바로 이전 값과 비교해 현재값이 크다면 현재 dp[] 에서 제일큰 값의 +1를 해주고 작다면 초기화된 값을 갖도록 했다. 문제에서는 가장 긴 수열이라고 주어졋기 때문에 따로 값을 넣어주진 않았다. import java.io.*; import java.util.*; class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLi..

문제 풀이 이 문제는 동적 계획법을 이용하여 풀었다. 이유는 2x1, 2x2를 이용하여 더 큰 타일의 경우의 수를 생각할 수 있다고 생각했고 최적 부분 구조로 바텀업 방식을 이용해서 풀 수 있을 거라고 생각했다. 우선 점화식을 세워보기 위해 직접 그려봤는데 이러한 경우의 수가 나왔다. 1,2,3,5 순으로 늘어나며 피보나치 수를 구하는 것과 비슷하다는 생각이 들었다 2x5는 직접 그려보면 알 수 있듯이 8개가 나온다. 이 결과를 갖고 점화식을 세워 보면 dp [n]=dp [n−1]+dp [n−2]라는 식을 세워 볼 수 있고 이 식으로 구현하여 문제를 풀 수 있었다. import java.io.*; class Main{ public static void main(String[] args) throws IO..

문제 풀이 문제를 바로 이해하진 못했지만 이해만 한다면 쉽게 풀 수 있는 문제이다. 후위 표기식은 연산이 뒤에 등장하는 식으로 ABC*+ 라면 ABC*이 A?(B*C)가 된뒤에 +가 오게 되면 A+(B*C) 가되는것이다. 쉽게 말해 문자가 아닌 연산이 오게 되면 앞에 문자 2개를 연산에 의해 계산해주면 된다. 연산이 나오면 최근에 PUSH한 값을 연산해 주는 것이므로 Stack을 사용하면 쉽게 풀 수 있다. import java.io.*; import java.util.*; class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamRea..