.

문제18248번: 제야의 종풀이1모든 사람(1~4)은 자리가 고정되어있고, 타종이 시행될 때마다 종 소리가 도달하는 거리는 다르다.따라서 들은 사람(1)과 못 들은 사람(0)이 생긴다. 첫 번째 타종이 수행됐을 때, 사람 1은 들었는데 사람 2는 못 들었다면 종으로부터의 거리는 (사람1 두 번째 타종이 수행됐을 때, 사람 2는 들었는데 사람 1은 못 들었다면 종으로부터의 거리는 (사람1 > 사람2)이다. 이 두 상황은 모순이다.따라서 각각의 타종이 울렸을 때를 비교해서 모순되는 경우를 찾으면 된다. 예제) 타종 M번사람N명 123410001200003000041110 예제의 경우, 세 번째 타종에서 사람 1은 못 들었고(0) 사람 4는 들었다(1).네 번째 타종에서 사람 1은 들었고(1) 사람 4는 못 ..

문제14496번: 그대, 그머가 되어 풀이알고리즘을 굉장히 오랜만에 풀어서 감을 다 잃었다 ^^.. 일단 어떤 알고리즘을 사용해야 하는지도 떠오르지 않아서그냥 인접리스트를 만들고 재귀로 모든 경로를 돌려서 a->b가 가능한지 찾았다. 코드1import java.io.*;import java.util.Arrays;import java.util.StringTokenizer;public class boj_14496 { static int[][] arr; static int b, ans = -1; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new In..

문제16973번: 직사각형 탈출 (acmicpc.net)풀이BFS를 이용해 Sr, Sc에서 시작해서 상하좌우로 한 칸씩 이동 가능한지 확인하며 모든 좌표를 탐색한다.작은 직사각형 범위 안에 벽(1)이 있거나 직사각형이 격자의 범위를 벗어나면 해당 경우는 이동할 수 없음이미 방문한 좌표이면 이동할 수 없음시작 좌표가 Fr, Fc에 도달하면 지금까지 움직인 거리를 출력한다. 직사각형 범위 안에 벽이 있는지 확인할 때, 직사각형의 모든 좌표를 탐색하면 시간초과가 발생한다. //시간초과import java.awt.*;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Lin..

문제14226번: 이모티콘 (acmicpc.net)화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.화면에 있는 이모티콘 중 하나를 삭제한다.풀이첫 시도복붙 : 약수 x를 찾아 dp[S] = min(dp[x1] + S/x1, dp[x2] + S/x2, ...)를 수행삭제 : 복붙이 모두 완료된 dp에서 모든 수 i에 대해 j기준 역순으로 dp[i]와 dp[j]+(삭제하는 시간)을 비교해 삭제가 더 빠른지 확인 dp[i] = min(dp[i], dp[j]+(j-i)) 테케와 질문게시판의 반례는 맞았지만 오답처리됨import java.util.*;import java.io.*;public class Main { static int S; ..

문제14594번: 동방 프로젝트 (Small) (acmicpc.net)풀이첫 시도 배열에 1~N의 숫자를 넣어두고, a부터 b까지의 숫자를 a로 모두 바꾸도록 했다.import java.util.*;import java.io.*;public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); StringTokenizer s..

문제1342번: 행운의 문자열 (acmicpc.net)풀이입력값이 작기 때문에 백트래킹으로 풀었는데 메모리 초과가 발생했다.행운의 문자열을 만들 수 있는 모든 경우를 빠짐 없이 실행하기 때문이다. 만약 aabbbaa라면, abababa 한 가지가 답이다.그러나 abababa를 만드는 모든 경우를 실행한다.이때 재귀호출에 의해 너무 많은 배열이 생성된다.import java.io.*;import java.util.*;public class boj_11508 { static String[] arr; static HashSet hs = new HashSet(); public static void main(String[] args) throws IOException { Buffere..

문제29704번: 벼락치기 (acmicpc.net)N개 T일 내에 제출 못 하면 벌금벌금의 최소 금액을 출력하라풀이먼저 모든 조합을 찾는 방법을 생각했고, 다음으로 그리디를 떠올렸다. 그리디 기준 -> 벌금이 큰 날부터? 소요 일수가 작은 날부터?객체를 만들어서 일수, 벌금을 저장한 후 리스트에 넣어 벌금 기준으로 정렬하고, 벌금이 같다면 소요 일수가 작은 순서로 정렬하기로 했다.1. 벌금이 큰 순서로 정렬 2. 벌금이 같다면 소요 일수가 작은 순서로 정렬 3. 앞에서부터 (T >= 소요일수)이면 선택 import java.io.*;import java.util.ArrayList;import java.util.Collections;import java.util.List;import java.util.St..

문제20117번: 호반우 상인의 이상한 품질 계산법 (acmicpc.net)묶음 -> 모든 호반우의 품질이 '중앙값'이 됨중앙값 = 짝수 : (묶음 개수/2) +1번째 숫자 홀수 : (묶음 개수+1) /2번째 숫자최대 이익을 출력풀이묶음이 짝수, 홀수인 경우 나눠서 값을 계산하고, 가장 큰 값을 출력해야 한다. 최대한 큰 값이 선택되게 해야 한다. -> 묶인 개수가 짝수면 '중앙+1' 에 가장 큰 값을 위치시켜야 한다.-> 묶인 개수가 홀수면 '중앙'에 가장 큰 값을 위치시켜야 한다.최대한 큰 값을 최대한 많이 선택하게 해야 한다. -> 묶음의 개수가 많을 수록 최대값이 더 많이 선택된다? -> 맞음-> 묶음 내의 호반우 개수가 많을 수록 최대값이 더 많이 선택된다? -> 아님 처음에는 중간값의 의미를 ..

문제14400번: 편의점 2 (acmicpc.net)모든 고객들의 거리의 합을 최소로 하는 위치에 편의점을 세울 때,그 최소 거리의 합을 출력하는 문제.풀이고객의 위치가 x, y좌표로 주어졌다.편의점이 세워질 위치를 모두 탐색하는 방법은 시간 초과를 발생시키므로 옳지 않다. 여러 점이 있을 때 그 점들과의 거리의 합을 최소화하는 지점은 정렬된 데이터의 '중간값'이다. 중간값 위치 기준 왼쪽, 오른쪽 사람 수가 비슷해지는데, 이때 어느 한쪽으로 위치를 이동시키더라도 전체 거리의 합이 증가할 수밖에 없으므로 중간값이 최적의 값이 된다. 답을 평균값으로 생각하기 쉬운데, 거리에 관한 문제라서 평균값은 오히려 거리를 증가시킬 수 있다.  1차원으로 예시를 들면 위치 2, 5, 20에 사람이 있다고 가정하자.평균..

문제22860번: 폴더 정리 (small) (acmicpc.net)풀이파일 구조를 보고 경로에 어떤 파일이 있는지 출력하는 문제이다. 어떤 자료구조를 사용해야 할지 먼저 고민했다. 제한 메모리가 1024MB로 충분히 컸기 때문에 다중 연결리스트를 써도 되지 않을까 생각했는데 폴더가 최대 1,000개인데 depth가 1,000인 연결 리스트를 만들어도 괜찮을지 모르겠다.  폴더이면 (C==1) 상위 폴더에 연결리스트를 추가한다.파일이면 (C==0) 상위 폴더에 파일 번호를 추가한다.일단 이렇게 아이디어를 떠올렸다.생각해보니 새로 연결리스트를 만들어서 그 자리에 넣는 게 아니라 새로 만든 리스트의 주소를 넣어도 될 것 같다. 그게 그거긴 한 것 같다. 어차피 포인터를 넣는 거니까...? 그러니까 폴더마다 연..