두부의 코딩일기

https://www.acmicpc.net/problem/1052 1052번: 물병 지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번 www.acmicpc.net 풀이 문제를 보자마자 '2'로 무언가를 해야한다는 걸 알았다. 하지만 쉽게 찾을 수가 없었고 이것저것 해보다가 2진수를 발견했다. 우선 숫자 N을 Integer.toBinaryString(N)을 이용해서 2진수로 변경해주면 된다. String binary = Integer.toBinaryString(N); 이 문제의 핵심은 2진수로 변경된 숫자 '1'의 개수를 보면 된다. 예제 2번에서 숫자 N(13)..

https://www.acmicpc.net/problem/1002 1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. www.acmicpc.net 풀이 처음 문제를 봤을 때 이해가 잘 안갔다.. 검색을 하고나서야 이해가 갔다. 하나씩 이해해보겠다. 문제에선 두 개의 터렛 x, y 좌표와 류재명과의 r1, r2가 제공된다. 그렇다면 x, y를 기준으로 r1, r2의 반지름을 가진 원을 그릴 수 있다. 두 개의 원이 그러졌다면 A 터렛의 원과 B 터렛의 원의 접점 개수를 구하면 된다. 두 개의 원을 그렸을 때 생기는 접점의 개수에 대한 경우의 수는 몇 개일까? 위 그림처럼 여러가지가 있겠지만 4가..

https://www.acmicpc.net/problem/1652 1652번: 누울 자리를 찾아라 첫째 줄에 방의 크기 N이 주어진다. N은 1이상 100이하의 정수이다. 그 다음 N줄에 걸쳐 N개의 문자가 들어오는데 '.'은 아무것도 없는 곳을 의미하고, 'X'는 짐이 있는 곳을 의미한다. www.acmicpc.net 풀이 dfs, bfs 문제처럼 보이지만 쉽게 풀 수 있는 문제이다. 문제의 조건은 아래와 같다. 1. 2칸 이상의 빈 칸이 있으면 누울 수 있다. 2. 반드시 벽이나 짐에 닿게 된다. 이중 for문을 돌리면서 가로, 세로에 연속 2칸이 비어있으면 cnt++을 해준 후에 break; 문으로 for문을 빠져나왔다. 하지만 이렇게 하니까 예외 상황이 하나 생겼다. 바로 한 줄에 2개의 자리가 ..

https://www.acmicpc.net/problem/1085 1085번: 직사각형에서 탈출 한수는 지금 (x, y)에 있다. 직사각형은 각 변이 좌표축에 평행하고, 왼쪽 아래 꼭짓점은 (0, 0), 오른쪽 위 꼭짓점은 (w, h)에 있다. 직사각형의 경계선까지 가는 거리의 최솟값을 구하는 프로그램 www.acmicpc.net 풀이 엄청 쉬운 문제라서 풀이라고 할 것도 없다. 주어진 변수는 총 4개 한수의 위치를 알려주는 x, y 우측 상단 꼭짓점을 알려주는 w, h 직사각형의 경계선까지 도달하는 최소 거리는 왼쪽, 오른쪽, 위, 아래 총 4가지이다. x, y, w-x, y-h의 최솟값을 구하면 된다. 최소값을 구하는 방법은 Math.min 혹은 if-else문을 사용하면 된다. 필자는 Math.mi..

https://www.acmicpc.net/problem/1475 1475번: 방 번호 첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 오랜만에 쉬운 문제 등장. 0-9번까지 숫자를 넣어주기 위한 cnt 배열을 생성해주고, 방 번호 N을 charAt으로 잘라서 배열에 입력해준다. charAt으로 잘라서 int형 배열에 입력하게 되면 아스키코드 값으로 변환되서 들어오기 때문에 숫자 1로 변경해주기 위해서 아스키코드 값이 48인 '0'을 빼주면서 배열에 입력해준다. int num = N.charAt(i) - '0'; 배열에 입력해줄 때 해당 숫자의 인덱스를 +1 시켜주면 된다. 또한 6과 9를 뒤집어서 사용할 수 있기 때문에 ..

https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 풀이 이번 문제는 예제가 7개나 있는 고마운 문제이다. 매번 알고리즘 문제를 풀면서 반례를 찾는게 여간 쉬운 일이 아닌데 정말 고맙다. 8x8 이상의 크기를 입력하고 상하좌우 한 칸씩 색깔이 다른 8x8 크기의 체스판을 만드는데 색칠이 잘 못된 최소 개수를 구하는 문제이다. 만약 10x10 크기의 배열이 입력됐다고 하면 자를 수 있는 경우의 수는 얼마나 될까? 10x10 크기가 주어지면 경..

https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 풀이 문제 설명이 매우 길어서 어렵게 느껴지지만 생각보다 쉬운 문제이다. N개의 도시와 N-1개의 도로가 있다. 그리고 도시에는 리터당 가격이 적혀있고 1리터당 1km를 갈 수 있다. 최소한의 비용으로 도시 A부터 D까지 가려면 어떻게 해야 될까? 바로 리터당 가격이 저렴한 기름을 넣는 것이다. 예제를 한 번 풀어보겠다. 첫 번째 도시에서 두 번째 도시로 가려면 5원짜리 기름을 2L..

https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 풀이 회의가 겹치지않도록 최대한 많은 회의를 배정하는 게 이 문제의 목표이다. 쉽게 말해서 이전 회의 종료 시간과 이후 회의 시작 시간이 겹치지 않으면 된다. 그리고 최대한 많은 회의를 하려면 종료 시간이 짧은 회의를 선택해야한다. 우선 문제를 쉽게 해결하기 위해서 종료 시간을 오름차순으로 정렬해야한다. Arrays.sort(times, new Comparator() { @Override public int compare(int[] o1, int[] o2) { // 종료 시간이 같다면 시작 시간이 빠른순으로 정렬..

https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 풀이 이번 문제는 잘 이해한다면 쉽게 풀 수 있다고 생각한다. 55-50+40 어떻게 하면 최솟값을 만들 수 있을까? 최솟값을 만들려면 최대한 큰 값을 빼주면 된다. 즉, 덧셈을 먼저 진행한 후에 뺄셈을 진행하면 된다. 1. 공식에서 -로 분리한다. String[] str = br.readLine().split("-"); 2. 이후에 +를 분리해서 값을 더해준다. for (int i=0; i

https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 풀이 브루트 포스 기법을 이용해서 해결하는 알고리즘 문제라고 한다. 사실 브루트 포스 기법이 뭔지 잘 모르는 상태에서 풀었다... 문제를 푸는 순서는 아래와 같다. 1. 9명의 난쟁이 키를 더한다. 2. 난쟁이 키를 오름차순으로 정렬한다. 3. 9명의 난쟁이 키를 합한 값에서 100을 뺀 후, 가짜 난쟁이 두 명을 더한 값과 비교한다. import java.io.*; import java.util.*; p..