문제 N행 M열의 표 A가 있고, 표의 각 칸에는 숫자가 하나씩 적혀있다. 연두는 서로 다른 1개 이상의 칸을 선택하려고 하는데, 행의 번호가 선택한 순서대로 등차수열을 이루고 있어야 하고, 열의 번호도 선택한 순서대로 등차수열을 이루고 있어야 한다. 이렇게 선택한 칸에 적힌 수를 순서대로 이어붙이면 정수를 하나 만들 수 있다. 연두가 만들 수 있는 정수 중에서 가장 큰 완전 제곱수를 구해보자. 완전 제곱수란 어떤 정수를 제곱한 수이다. 입력 첫째 줄에 N, M이 주어진다. 둘째 줄부터 N개의 줄에는 표에 적힌 숫자가 1번 행부터 N번 행까지 순서대로 한 줄에 한 행씩 주어진다. 한 행에 적힌 숫자는 1번 열부터 M번 열까지 순서대로 주어지고, 공백없이 모두 붙여져 있다. 출력 첫째 줄에 연두가 만들 수..
개발자
문제 오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이다. 이제 스타트 팀과 링크 팀으로 사람들을 나눠야 한다. 두 팀의 인원수는 같지 않아도 되지만, 한 명 이상이어야 한다. BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다. N=4이고, S가 아래와 같은 경우를 살펴보자..
문제 세 수 x, y, z가 x+y>z, x+z>y, y+z>x의 관계를 만족하면, 세 수는 삼각관계에 있다고 한다. 마찬가지로 길이가 N인 수열 B(b[0], b[1], ..., b[n-1])의 모든 b[i], b[j], b[k]가 삼각관계에 있으면 이 수열은 삼각 수열이라고 한다. 이때, i, j, k는 모두 다른 값이다. 수열 A가 주어졌을 때, 이 수열에서 적절히 몇 개의 원소를 빼서 이 수열을 삼각 수열로 만들려고 한다. 삼각 수열의 최대 길이를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수열의 크기 N이 주어진다. 둘째 줄에 수열 A에 들어있는 수가 공백을 사이에 두고 주어진다. N은 최대 50이고, A에 들어있는 수는 109보다 작거나 같은 자연수이다. 출력 첫째 줄에 가장 긴 부분 삼각..
문제 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 12으로 표현할 수도 있다. 역사적으로 암산의 명수들에게 공통적으로 주어지는 문제가 바로 자연수를 넷 혹은 그 이하의 제곱수 합으로 나타내라는 것이었다. 1900년대 초반에 한 암산가가 15663 = 1252 + 62 + 12 + 12라는 해를 구하는데 8초가 걸렸다는 보고가 있다. 좀 더 어려운 문제에 대해서는 56초가 걸렸다: 11339 = 1052 + 152 + 82 + 52. 자연수 n이 주어질 때, n을 최소 개수의 제곱수 합으로 표현하는 컴퓨터 프로그램을 작성하시오. 입력 입력은 ..
import java.io.*; import java.util.*; public class Main { static BufferedReader br; static StringTokenizer st; static int N; static int[] arr; static int[][] states; static boolean[] nums; static int res; public static void main(String[] args) throws IOException { input(); solve(); System.out.println(res); } static void input() throws IOException { br = new BufferedReader(new InputStreamReader(S..
import java.io.*; import java.util.*; public class Main { static BufferedReader br; static StringTokenizer st; static int A, T, F; public static void main(String[] args) throws IOException { input(); System.out.println(solve()); } static void input() throws IOException { br = new BufferedReader(new InputStreamReader(System.in)); A = Integer.parseInt(br.readLine()); T = Integer.parseInt(br.readLi..
배열로 무식하게 푸는 방법과 우선순위 큐를 이용해서 푸는 2가지 방법이 있었다. 첫번째로는 배열을 사용한 풀이인데 나는 우선 이것부터 떠올렸다. 매번 값을 받을 때 마다 sort를 해주어서 홀수번 째 마다 중앙값을 구해주면 됐는데 시간초과가 날줄 알았지만 간당간당하게 통과했다. 아무래도 수열의 크기가 크지 않아서 그랬던 듯 하다. 두번째 풀이는 min-heap과 max-heap을 이용한 풀이였다. 이건 다른 분들의 블로그를 참고해서 푼 문제이다. 확실히 배열로 풀었을 때 보다 최적화 면에서 더 나았다. 어떻게 이걸 바로 떠올리고 풀지라는 신기한 생각을 또 가지게 되었다. (__) 1. 중앙값의 개수 출력 => (N+1) / 2 2. 최대힙과 최소힙의 크기가 같다면 최대힙, 다르다면 최소힙에 값을 넣는다...
25년 간의 수행 끝에 원재는 미래를 보는 능력을 갖게 되었다. 이 능력으로 원재는 사재기를 하려고 한다. 다만 당국의 감시가 심해 한 번에 많은 양을 사재기 할 수 없다. 다음과 같은 조건 하에서 사재기를 하여 최대한의 이득을 얻도록 도와주자. 1. 원재는 연속된 N일 동안의 물건의 매매가를 예측하여 알고 있다. 2. 당국의 감시망에 걸리지 않기 위해 하루에 최대 1만큼 구입할 수 있다. 3. 판매는 얼마든지 할 수 있다. 예를 들어 3일 동안의 매매가가 1, 2, 3 이라면 처음 두 날에 원료를 구매하여 마지막 날에 팔면 3의 이익을 얻을 수 있다. [입력] 첫 번째 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스 별로 첫 줄에는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘..
import java.io.*; import java.util.*; public class Laboratory { static int[] dx = {-1, 1, 0, 0}; static int[] dy = {0, 0, -1, 1}; static BufferedReader br; static StringTokenizer st; static int n, m; static int res = Integer.MIN_VALUE; static int[][] map, copyMap, virusMap; public static void main(String[] args) throws IOException{ input(); solve(0); System.out.println(res); } static void input(..
import java.io.*; import java.util.*; public class FourIntegersWithSumOfZero { static BufferedReader br; static StringTokenizer st; static int n; static long ans; static int[] a, b, c, d; static long[] left, right; public static void main(String[] args) throws IOException{ input(); calculate(); Arrays.sort(left); Arrays.sort(right); getSum(); System.out.println(ans); } static void input() throws..
