목록코딩테스트/백준 (18)
최코딩의 개발노트
사이트 https://www.acmicpc.net/problem/20310 20310번: 타노스 어느 날, 타노스는 0과 1로 이루어진 문자열 $S$를 보았다. 신기하게도, $S$가 포함하는 0의 개수와 $S$가 포함하는 1의 개수는 모두 짝수라고 한다. 갑자기 심술이 난 타노스는 $S$를 구성하는 문자 www.acmicpc.net 문제 분석 실버3 문제여서 굉장히 얕본 문제였지만 의외로 어렵게 푼 문제였다... 필자는 문자열 알고리즘이 너무 약한거 같다. 자 이제 분석을 들어가보자! 처음 생각 필자의 처음생각은 간단했다! 그냥 1하고 0 갯수 샌 다음에 바로 절반으로 나누고 문제가 요구한게 사전순이므로 그냥 0부터 쭉 갯수 대로 나열하면 될거라고 생각했다. 너무 간단하고 이게 실버문제인가... 의심을 ..
사이트 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 문제 분석 쉬울거 같았지만 매우 헷갈리고 어려웠던 문제였다... 처음에 bfs로 구현할려 했지만 퍼지면서 청소하는 것이 아닌 깊이 있게 가서 청소를 하는 것이 맞아서 최종적으로 dfs를 선택하였다. 입력은 첫번째 줄에 청소할 크기를 받고 두번째 줄에 시작위치와 방향을 입력받는다. 0 북, 1 동, 2 남, 3 서 이다. 조건을 자세히 봐야 ..
사이트 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 분석 x가 3으로 나누어 떨어지면 3으로 나누고 x가 2로 나누어 떨어지면 2로 나누고 2개가 해당이 안될시에 1을 빼면 된다. 쉬울꺼 같지만 의외로 복잡하다. 애매한게 주어진 숫자가 10일때를 생각해보자 10 9 3 1 10 5 4 2 1 위 경우의 수를 볼때 먼저 1을 빼면 경우의수가 4가 나오지만 2로 나눌때는 5가지가 된다.. 또한 6같은 경우는 2하고 3 동시에 나눌 수 있기 때문에 뭔가 애매하다. 그래서 거꾸로 생각했다! 처음 숫자를 토대로 나누지말고 맨 아래로 들어가서 경우의 수를 구하..
사이트 https://www.acmicpc.net/problem/16929 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net 문제 풀이 문제는 간단했다. 똑같은 문자를 기준으로 1개의 순환 구조만 있으면 Yes 아니면 No만 뜨게 하는 문제이다. 필자는 당연히 dfs로 생각해서 풀었다. 맨날 bfs로만 풀어서 익숙치 않았지만 이 문제는 dfs로 해결을 해야될거 같아서 풀어봤다. BufferedReader br = new BufferedReader(new InputStreamReader(System.in)..
사이트 https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 분석 뭔가 간단하면서 조금 헷갈린 문제였다. 먼저 입력이 아래와 같으면 4 2 9 7 9 1 출력이 아래와 같이 나와야된다. 1 7 1 9 7 1 7 9 9 1 9 7 9 9 즉 중복되는 것만 빼면 된다. 중복을 안빼면 1 7 1 9 1 9 이렇게 2개의 1 9가 나오는 것이다. 그래서 필자는 가장먼저 Set을 생각했다. if (depth == m) { StringBuilder sb..
사이트 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 문제 분석 약 5시간만에 푼문제였다... 어렵지 않다 생각했는데 매우 복잡했던 문제였다.(리펙토링 무조건 보기!!) 5 2 0 2 0 1 0 1 0 1 0 0 0 0 0 0 0 2 0 0 1 1 2 2 0 1 2 입력이 다음과 같으면 출력은 10이 나와야된다. 즉 입력부분에서 치킨집 즉 2가 5개 이므로 이 중 2개를 뽑아 집 즉 1과 거리가 최소가 나는 기준으로 치킨..