boj

안녕하세요. delay100 입니다. 미들러 문제. 제리와 톰 2 https://www.acmicpc.net/problem/17504 17504번: 제리와 톰 2 $$ 1 - \cfrac{1}{2 + \cfrac{1}{7 + \cfrac{1}{1 + \cfrac{1}{8}}}} = 1 - \cfrac{1}{2 + \cfrac{1}{7 + \cfrac{8}{9}}} = 1 - \cfrac{1}{2 + \cfrac{9}{71}} = 1 - \cfrac{71}{151} = \cfrac{80}{151} $$ www.acmicpc.net 분모와 분자를 바꿔주며 계산하면 됩니다. import java.io.*; import java.util.*; public class Main { public static void..

1. 문제 https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 2. 접근 및 해결 2-1) 접근 이 문제를 풀기 위해 한 cctv에서 고려해야 할 것은 종류, 위치, 방향으로 총 3가지 입니다. 그런데 종류, 위치는 이미 문제에서 주어지기 때문에 우리는 방향만 정하면 됩니다. 종류, 위치(x, y), 방향에 대한 정보 는 cctv 리스트로 관리할겁니다. 위치는 x좌표, y좌표가 있으므로 총 4가지의 정보를 담아야 합니다. int[][] ..

1. 문제 https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 2. 접근 및 해결 2-1) 접근 1. 백트래킹으로 해결 2. 중복 없이 M개를 고른 수열 + 오름차순 -> 현재 나온 숫자가 다음에 나올 숫자보다 크면 출력하지 않음 2-2) 해결 if(cnt==M) { StringBuilder sb2 = new StringBuilder(); for(int i=0; ilist[i+1]) return; // 이 코드를 빼면 15649번 풀이와 같아짐 ..

1. 문제 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 2. 접근 및 해결 2-1) 접근 1. bfs로 접근합니다. 2. 3차원 배열(isVisited)을 이용합니다. isVisited[부순 벽인지][x][y]로 작성했습니다. -> 부순 벽인지? 0:부수지 않고 옴, 1: 부숴서 옴 부수지 않고 현재 x, y좌표까지 왔는지? 부숴서 현재 x, y좌표까지 왔는지를 나타냅니다. 3. Node는 x, y, cnt(현재까지..

1. 문제 https://www.acmicpc.net/problem/6198 6198번: 옥상 정원 꾸미기 문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으 www.acmicpc.net 이 문제를 풀기 바로 전에 풀었던 탑 문제와 유사하다. https://delay100.tistory.com/108 [BOJ] 백준 2493번: 탑_자바(JAVA) 1. 문제 https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 ..

1. 문제 https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 2. 접근 및 해결 2-1) 접근 Stack이 pop되면서 변경되는 index를 처리하기 위해 Top이라는 객체를 만들어줬습니다. 이렇게 객체로 만들지 않으면, 스택이 pop되면서 현재 index위치를 잃어버리게 됩니다. 이 객체를 만들기 전에는 이중 for문으로 처리했었는데, 그럼 시간초과에서 벗어날 수가 없어서 채용했습니다.. class Top { int index; int hei..

1. 문제 https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 2. 접근 및 해결 2-1) 접근 Stack stk = new Stack(); int num = 1; // (앞으로) 스택에 추가할 값 (1

1. 문제 https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 2. 접근 및 해결 2-1) 접근 투포인터를 사용하지 않고 구현하는 방법입니다. // 입력 9 5 12 7 10 9 1 2 3 11 13 int[] numList = new int[num]; // [5, 12, 7, 10, 9, 1, 2, 3, 11] int[] list = new int[2000001]; 먼저 입력으로 들어오는 a..

1. 문제 https://www.acmicpc.net/problem/1267 1267번: 핸드폰 요금 동호가 저번 달에 이용한 통화의 개수 N이 주어진다. N은 20보다 작거나 같은 자연수이다. 둘째 줄에 통화 시간 N개가 주어진다. 통화 시간은 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 2. 접근 및 해결 2-1) 접근 문제에서 주의할 점은 아래의 단락입니다. 영식 요금제는 30초마다 10원씩 청구된다. 이 말은 만약 29초 또는 그 보다 적은 시간 통화를 했으면 10원이 청구된다. 만약 30초부터 59초 사이로 통화를 했으면 20원이 청구된다. 민식 요금제는 60초마다 15원씩 청구된다. 이 말은 만약 59초 또는 그 보다 적은 시간 통화를 했으면 15원이 청구된다. 만약 ..

1. 문제 https://www.acmicpc.net/problem/2480 2480번: 주사위 세개 1에서부터 6까지의 눈을 가진 3개의 주사위를 던져서 다음과 같은 규칙에 따라 상금을 받는 게임이 있다. 같은 눈이 3개가 나오면 10,000원+(같은 눈)×1,000원의 상금을 받게 된다. 같은 눈이 2개만 www.acmicpc.net 2. 접근 및 해결 2-1) 접근 문제에는 아래와 같은 조건이 존재합니다. 같은 눈이 3개가 나오면 10,000원+(같은 눈)×1,000원의 상금을 받게 된다. 같은 눈이 2개만 나오는 경우에는 1,000원+(같은 눈)×100원의 상금을 받게 된다. 모두 다른 눈이 나오는 경우에는 (그 중 가장 큰 눈)×100원의 상금을 받게 된다. 처음 봤을 때 IF문을 많이 쓰면 금..