본문 바로가기

IM대비

(18)
백준 14696 <딱지놀이> 각각의 라운드마다 A B 배열을 만들고 개수를 확인하면서 출력하는 문제이다. 전체 코드 더보기 package asd; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class sad { public static void main(String[] args) throws IOException { int n,k; BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); n=Integer.parseInt(br.readLine()); for(int ..
백준 13300 <방배정> 이 문제의 핵심은 각 학년의 성별에 따라 k로 몇 번 나눠지고 나머지가 있는지 여부를 판단하는 문제이다. 전체 코드 더보기 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main{ public static void main(String[] args) throws IOException { int n,k,result=0; int map[][]=new int[2][7]; BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Stri..
백준 10163 <색종이> 이전의 비슷한 문제들을 IM에서 많이 본 것 같다. IM문제는 대부분 이중 for문과 그 값을 저장하는 문제 위주로 내는 것 같다. 문제 풀이 각각의 시작점에서 높이와 너비만큼 이차원 map에 자신의 색종이 넘버를 입력 다음 색종이가 겹치게 된다면 그대로 덮어씌운다. 색종이 수만큼 map에 다 입력했다면 map [][]에 적힌 번호의 결과 값을 증가시킨다. 전체 코드 더보기 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main{ public static void main(String[] args) th..
백준 2559 <수열> 투 포인터의 개념을 이용하여 접근이 가능한 문제!! 이 문제에서 조금 응용을 해 k일의 온도 합을 구하는 것이 T번 있다고 가정하면 인덱스 트리를 이용하게 되는 문제! 문제 풀이 처음 K수만큼을 sum 값에 더한다. start를 0 finish를 k로 두고 하나씩 증가하며 finish가 n이 될 때까지 진행한다. sum값에 finish를 더하고 start를 빼주고 이렇게 최대를 구한다 전체 코드 더보기 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collections; import java.util.Str..
백준 2304 <창고 다각형> 위의 그림을 보게 되면 어떻게 구해야 할지 감이 오는 문제. 앞에서부터 시작해서 점점 커지는 기둥만 넣고 반대로 뒤에서부터 시작해서 점점 커지는 기둥을 넣고 계산하면 끝! 문제 풀이 기둥의 시작위치가 랜덤 하기 때문에 class를 하나 만들어서 시작 위치 순으로 정렬 가작 작은 위치부터 시작해서 증가하면서 커지는 기둥만 ArrayList에 넣기 그림에서는 2 반대로 가장 높은 위치에서 시작해서 감소하면서 커지는 기둥만 ArrayList에 넣기 그림에서는 15 Arraylist에서 이전값의 h에다가 사이의 값을 곱해서 더하기 마지막으로 가장높은 위치 한번 더 더해주기 주의 사항! 이렇게 해주게 되면 이렇게 색칠한 부분이 들어가지 않는다. 처음부터 시작한 것이 6,8 이 끝이고 뒹서부터 시작한 것이 8,8 ..
백준 2116 <주사위쌓기> 시뮬레이션 완전 탐색 문제이다. 문제가 어렵지는 않지만 시뮬레이션을 처음 접한다면 많은 생각이 필요한 문제. 문제를 이해하기 위해서는 기본적으로 주사위밑면이 어떤 부분일 경우 윗면이 어떤 부분이 온다는 것을 인지해야 하는 문제이다. 이렇게 세트로 온다는 것을 잘 생각해야 한다. 이 문제의 시간 복잡도는 맨처음 6가지를 고르는 경우와 다음 6개 중 한 개가 정해져 있기 때문에 최대 10000개 이하이기 때문에 6*6*10000 이므로 36만이고 옆면 중 최댓값을 찾는 경우 각각 6이라고 가정하면 6*6*10000을 한 번 더 하기 때문에 대략 72만이 될것이다. 문제 풀이 처음 시작은 6개 경우 다해봐야 함 아랫부분과 위를 제외한 최댓값을 구한다 다음 함수의 매개변수에 현재 위에 올 숫자와 이때까지의 합과..
백준 2628 <종이자르기> IM 대비 문제 치고는 많이 생각할 점이 있는 문제였다. 이 문제의 핵심은 자른 색종이의 가로와 세로가 가장 큰 길이를 찾는 것이다. 문제 풀이 가로 세로 가장 긴 길이를 탐색하기 위해 각각의 ArrayList에 넣고 정렬을 했다. 투 포인터라는 개념을 기준으로 시작점을 0으로 잡고 하나씩 꺼내 사이의 간격을 비교해준다. 이렇게 가로 세로가 구해지면 곱해준다. 시작점을 0 으로 잡고 다음 지점과 간격을 비교하고 시작점을 이동하고 그렇게 끝까지 계산하면 가장 긴 길이를 구할 수 있다.! 마지막에는 마지막 자른 위치와 총길이를 빼주는 계산이 필수!! 예를 들어 세로 부분 3이 마지막이므로 총길이 8에서 3을 빼주는 것도 포함! 1번 순서 ArrayList에 넣고 정렬! 위에 부분이 가로 아래부분이 세로 전체..
백준 1244 <스위치 켜고 끄기> 시뮬레이션 문제 남학생 여학생인지 확인해서 완전 탐색을 하는 문제이다 이 문제의 시간 복잡도는 스위치 개수와 학생의 수를 곱한 100*100=1만이다. 문제 풀이 남학생 여학생의 경우를 판단 남학생일 경우 배수만큼 이동하면서 바꿔주기 여학생일 경우 그점을 기준으로 양옆으로 가면서 확인 이 문제에서는 System.out.print() 를 사용하는 시간을 줄이기 위해 StringBuilder를 사용해 시간을 단축했다. 전체 코드 더보기 package asd; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class s..
백준 2635 <수 이어가기> 이 문제는 기본적으로 첫 번째 정수를 2로 나눈 것 이상의 수를 두 번째 수로 잡고 전부 계산해보는 문제이다. n을 2로 나눈것 이상을 두 번째 수로 하는 이유는 그렇지 않으면 항상 3번째 오는 수는 2번째 수보다 클 것이고 결과는 3이 나오기 때문이다. 예를 들자면 50 25 25 0 50을 2로 나눈수를 두 번째로 가진 경우 50 23 27 결국 50을 2로 나눈수 25 보다 작으면 세 번 재수는 항상 2번째 수보다 크기 때문이다. 즉 25 미만의 숫자는 50을 2로 나눈 수부터 시작한것보다 전체 크기가 작다. 문제 풀이 n/2로 나눈 수 부터 전부 다 돌려본다. ArrayList를 이용해서 ArrayList 크기가 현재 결과 ArrayList 크기보다 크다면 옮겨 담는다. Stringbuilder을..
백준 2669 <직사각형 네개의 합집합의 면적 구하기> skygood95.tistory.com/42 백준 2563 색종이의 수가 100이하이고 흰색도화지 크기가 100이기때문에 완전탐색으로도 가능한 문제이다. 그렇지 않다면 인덱스 트리를 이용해서 풀어야하는 문제이다. 이 문제의 시간 복잡도를 계산한다 skygood95.tistory.com 이 색종이 문제랑 비슷한 유형으로 범위가 짧기 때문에 boolean형 map 이차원 배열을 이용해 체크해주고 후에 계산하는 문제 다만 주의해야 할점은 시작점 x , y 종료점 x, y 점을 입력받으면 1씩 감소시켜 시작점 x부터 종료점 x-1까지, 시작점 y부터 종료점 y-1까지 체크를 해주는게 포인트이다. 이러한 문제는 마찬가지로 범위를 계산해 시간초과가 되지 않는지 확인하는 게 중요하다. 문제 풀이 시작점 x부터 종료점..