문제 크기가 H×W인 모눈종이와 스티커 N개가 있다. i번째 스티커의 크기는 Ri×Ci이다. 모눈종이는 크기가 1×1인 칸으로 나누어져 있으며, 간격 1을 두고 선이 그어져 있다. 오늘은 모눈종이에 스티커 2개를 붙이려고 한다. 스티커의 변은 격자의 선과 일치하게 붙여야 하고, 두 스티커가 서로 겹치면 안 된다. 단, 스티커가 접하는 것은 가능하다. 스티커를 90도 회전시키는 것은 가능하다. 스티커가 모눈종이를 벗어나는 것은 불가능하다. 두 스티커가 붙여진 넓이의 최댓값을 구해보자. 입력 첫째 줄에 모눈종이의 크기 H, W, 둘째 줄에 스티커의 수 N이 주어진다. 다음 N개의 줄에는 스티커의 크기 Ri, Ci가 주어진다. 출력 첫째 줄에 두 스티커가 붙여진 넓이의 최댓값을 출력한다. 두 스티커를 붙일 수..
백준
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 128 MB 379 258 200 68.966% 문제 상우는 재미있는 게임을 생각해냈다. 동전 9개를 아래 그림과 같이 3행 3열로 놓는다. H는 앞면, T는 뒷면을 의미한다. H T T H T T T H H 게임의 목적은 이 동전의 모양을 모두 같은 면(H나 T)이 보이도록 하는 것이다. 단, 하나의 동전만을 뒤집을 수는 없고, 한 행의 모든 동전, 한 열의 모든 동전 또는 하나의 대각선 상의 모든 동전을 한 번에 뒤집어야 한다. 그런 식으로 세 개의 동전을 뒤집는 것을 '한 번의 연산'으로 센다. 상우는 이것을 최소 횟수의 연산으로 실행하고 싶어한다. 오랜 시간 생각한 끝에 위의 경우는 두 번의 연산으로 가능하다는 것을 알아냈고, 또, 이..
문제 라그랑주는 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 boolean[][] check; static int[] result; static boolean[] visited; static int N, M, cnt; public static void main(String[] args) throws IOException { init(); comb(1, 0); System.out.println(cnt); } static void init() throws IOException { br = new BufferedReader(new InputStreamReader..
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 String[] arr; static boolean[] checked; static int N, L; static StringBuilder minStr; static int min; public static void main(String[] args) throws IOException { input(); solve(); System.out.println(minStr); System.out.println(min); } static void input() throws IOException { br =..
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..
시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 512 MB 682 178 121 22.787% 문제 송훈이는 로봇 동아리 회원이다. 로봇 동아리에서 필요한 부품이 있을 경우 자유롭게 빌려서 쓰고 다시 돌려놓으면 된다. 하지만 부품 정리를 하다가 부품 관리가 너무 힘들어져 새로운 시스템을 도입하려고 한다. 부품을 빌려갈 경우 부품 대여장에 정보를 반드시 작성해야한다. 또한 빌려간 부품을 반납 할 경우에도 부품 대여장에 정보를 작성해야한다. 또한 대여기간을 정하고 대여기간을 넘길 경우 1분당 벌금을 부여하도록 하는 시스템이다. 만약 대여기간이 5분, 1분당 벌금이 5원이라 했을 때 대여한 시각이 2021년 1월 1일 1시 5분이라면 2021년 1월 1일 1시 10분까지 반납해야한다. 2021년 1월 ..
배열로 무식하게 푸는 방법과 우선순위 큐를 이용해서 푸는 2가지 방법이 있었다. 첫번째로는 배열을 사용한 풀이인데 나는 우선 이것부터 떠올렸다. 매번 값을 받을 때 마다 sort를 해주어서 홀수번 째 마다 중앙값을 구해주면 됐는데 시간초과가 날줄 알았지만 간당간당하게 통과했다. 아무래도 수열의 크기가 크지 않아서 그랬던 듯 하다. 두번째 풀이는 min-heap과 max-heap을 이용한 풀이였다. 이건 다른 분들의 블로그를 참고해서 푼 문제이다. 확실히 배열로 풀었을 때 보다 최적화 면에서 더 나았다. 어떻게 이걸 바로 떠올리고 풀지라는 신기한 생각을 또 가지게 되었다. (__) 1. 중앙값의 개수 출력 => (N+1) / 2 2. 최대힙과 최소힙의 크기가 같다면 최대힙, 다르다면 최소힙에 값을 넣는다...
이중 우선순위 큐 구현 문제였다. min-heap 과 max-heap 두개로 구현해볼까 했는데 뭔가 내가 전혀 모르는 방법이 있을 것 같아서 찾아보니 min-max-heap을 구현하는 방법과 c++의 STL 라이브러리에서 Multiset을 이용한 방법 그리고 내가 사용한 TreeMap을 이용한 구현 방법이 있었다. 먼저 나는 다른 알고리즘 문제를 풀면서 Map 자료구조 중에서는 항상 HashMap 만을 사용해왔었다. TreeMap은 내부가 레드 블랙 트리를 사용하고 있고 삽입, 삭제, 추가 모두 O(log n)의 시간복잡도가 나와서 HashMap 보다는 성능이 떨어진다. 하지만 범위의 검색을 하거나 최댓값, 최솟값을 찾을 때는 TreeMap을 사용하는 것이 효율적이다. 처음에는 구현할 때 중복으로 들어오..
