[Java] 백준 15684 (사다리 조작) Gold 4

Problem : https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net Approach 백트랙킹 Backtracking을 활용하여 BruteForce 완전탐색으로 풀이하였다. 가로선을 놓을 수 있는 개수는 0, 1, 2, 3개 이다. 이를 이용하여 문제를 푸는 주요 로직은 다음과 같다. 가로선을 놓을 수 있는 개수만큼 가로선을 놓아본다. 이 때, A 번째 사다리가 A 에 도착하는지를 검사한다. 모든 경우의 수에 대하여 위 과정을 수행한다. 생각하기..

→2021.06.14

Algorithm/Baekjoon Online Judge

[Java] 백준 17069 (파이프 옮기기 2) Gold 5

Problem : https://www.acmicpc.net/problem/17069 17069번: 파이프 옮기기 2 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net Approach DP 로 문제를 풀이했다. 백준 17070 (파이프 옮기기 1)와 똑같은 문제지만, 문제의 입력 부분에 차이가 있다. [java] 백준 17070 (파이프 옮기기 1) Gold 5 문제 원문 링크 : https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 ..

→2021.06.14

Algorithm/Baekjoon Online Judge

[Java] 백준 9944 (NxM 보드 완주하기) Gold 3

Problem : https://www.acmicpc.net/problem/9944 9944번: NxM 보드 완주하기 N×M 보드 위에서 할 수 있는 게임이 있다. 보드는 크기가 1×1인 정사각형 칸으로 나누어져 있다. 보드의 각 칸은 빈 칸 또는 장애물이다. 장애물은 아래 그림에선 어두운 사각형으로 표시되어져 www.acmicpc.net Approach BruteForce완전탐색 + 구현으로 문제를 풀이하였다. 문제풀이에 앞서 해당 문제는 입력의 끝이 정해져 있지 않다. 해당 내용에 관한 부분은 아래 포스팅을 참고하면 좋을 것이다. https://gre-eny.tistory.com/307 [Java] EOF(End Of File) 처리하기 EOF(End Of File) EOF(End Of File) 은..

→2021.06.13

Algorithm/Baekjoon Online Judge

[Java] 백준 17088 (등차수열 변환) Gold 4

Problem : https://www.acmicpc.net/problem/17088 17088번: 등차수열 변환 크기가 N인 수열 A = [A1, A2, ..., AN]이 있을 때, 모든 1 ≤ i < N에 대해서, Ai+1-Ai가 모두 일치하면 등차수열이라고 한다. 예를 들어, [3], [6, 6, 6], [2, 8, 14, 20], [6, 4, 2]는 등차수열이고, [4, 5, 4], [6, 3, 1] www.acmicpc.net Approach 등차수열의 공차 개념을 이용한 BruteForce(완전탐색)로 문제를 풀이하였다. 수열의 각 요소들에 -1, +1연산을 최대 1번 수행할 수 있다고 한다. 주의할 점은 0번 수행해도 된다는 것이다. 수열에서 연속된 두 요소의 차를 공차 라고 한다. 직전 숫..

→2021.06.12

Algorithm/Baekjoon Online Judge

[Java] 백준 16938 (캠프 준비) Gold 4

Problem : https://www.acmicpc.net/problem/16938 16938번: 캠프 준비 난이도가 10, 30인 문제를 고르거나, 20, 30인 문제를 고르면 된다. www.acmicpc.net Approach 조합(Combination)을 이용한 BruteForce(완전탐색)문제이다. 입력의 크기가 최대 15로 비교적 작으므로 가능한 풀이이다. 캠프에 사용할 문제를 고르는 전체 방법의 수는 nC2 + nC3 + ... + nCn이다. 이렇게 나온 결과 조합의 숫자들을 검증해주면 된다. 배열 요소의 총합, 최댓값, 최솟값은 Stream을 사용하여 간결한 코드로 구할 수 있다. Code import java.io.*; import java.util.Arrays; import java...

→2021.06.11

Algorithm/Baekjoon Online Judge

[Java] 백준 15683 (감시) Gold 5

Problem : https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net Approach BruteForce(완전탐색) + 구현 문제이다. 1 ~ 5번 연산을 구현해야 하고, 연산에 필요한 CCTV가 감시하고 있는 영역을 구현해야 한다. 먼저 1 ~ 5번 연산에 필요한 공통적인 부분을 구현해야 한다. (fiilLeft(), fillRight(), fillUp(), fillDown()) 위 4개 메소드는 현재 위치 (x, y)에서 XXX 방향..

→2021.06.11

Algorithm/Baekjoon Online Judge

[Java] 백준 16936 (나3곱2) Gold 5

Problem : https://www.acmicpc.net/problem/16936 16936번: 나3곱2 나3곱2 게임은 정수 하나를 이용한다. 가장 먼저, 정수 x로 시작하고, 연산을 N-1번 적용한다. 적용할 수 있는 연산은 두 가지 있고, 아래와 같다. 나3: x를 3으로 나눈다. x는 3으로 나누어 떨어져야 www.acmicpc.net Approach Backtracking으로 BruteForce(완전탐색)를 수행하는 문제이다. 만들 수 있는 모든 경우의 수를 탐색하기 위해 백트랙킹 기법을 사용하였다. 모든 숫자를 시작 숫자로 시도해 보아야 한다. 3으로 나누어 떨어지면, 3으로 나눈 수가 배열에서 아직 사용이 되지 않았는지 검사하고 재귀 호출한다. 2를 곱한 수가 배열에서 아직 사용이 되지 ..

→2021.06.10

Algorithm/Baekjoon Online Judge

[Java] 백준 17089 (세 친구) Gold 5

Problem : https://www.acmicpc.net/problem/17089 17089번: 세 친구 첫째 줄에 사람의 수 N(3 ≤ N ≤ 4,000), 친구 관계의 수 M(0 ≤ M ≤ 4,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계를 의미하는 두 정수 A, B가 주어진다. 친구 관계는 A와 B, 그리고 B와 A가 친 www.acmicpc.net Approach BruteForce(완전탐색) 문제이다. 먼저 입력을 받으면서 관계 배열 relations 을 구성한다. 또한, 특정 사람의 친구의 수를 기록한다. 세 친구 A, B, C 를 A = 0, B = 1, C = 2부터 시작하여 세 친구 ABC가 모두 친구인 경우를 찾고, 그 때의 최대 친구 수를 찾으면 된다. ABC의 친구를..

→2021.06.10

Algorithm/Baekjoon Online Judge

[Java] 백준 1981 (배열에서 이동) Gold 1

Problem : https://www.acmicpc.net/problem/1981 1981번: 배열에서 이동 n×n짜리의 배열이 하나 있다. 이 배열의 (1, 1)에서 (n, n)까지 이동하려고 한다. 이동할 때는 상, 하, 좌, 우의 네 인접한 칸으로만 이동할 수 있다. 이와 같이 이동하다 보면, 배열에서 몇 개의 수를 www.acmicpc.net Approach 이분탐색 + BFS 문제이다. 꽤 어렵게 문제를 풀었다. 문제 풀이에 앞서, 입력을 받으면서 구해놔야 할 것이 있다. 배열의 값중 최솟값 minNum과 최댓값 maxNum을 이분탐색의 left와 right에 이용하기 때문이다. left는 0이다. (배열의 값이 모두 같은 경우 최대 - 최소 = 0이다.) right는 maxNum - minN..

→2021.06.09

Algorithm/Baekjoon Online Judge

[Java] 백준 1561 (놀이 공원) Gold 2

Problem : https://www.acmicpc.net/problem/1561 1561번: 놀이 공원 첫째 줄에 N(1 ≤ N ≤ 2,000,000,000)과 M(1 ≤ M ≤ 10,000)이 빈칸을 사이에 두고 주어진다. 둘째 줄에는 각 놀이기구의 운행 시간을 나타내는 M개의 자연수가 순서대로 주어진다. 운행 시간은 1 이상 30 www.acmicpc.net Approach 이분탐색을 이용하여 풀이가 가능한 문제이다. 먼저 n이 m이하일 경우, 0초에 모든 사람들이 놀이기구에 탑승할 수 있으므로 n번째 놀이기구가 마지막 사람이 타는 놀이기구가 될 것이다. 위 경우가 아니라면, 문제를 푸는 주요 로직은 다음과 같다. 먼저 n -= m 을 수행한다. (0초에 m명이 놀이기구를 탈 수 있기 때문이다.)..

→2021.06.06

티스토리툴바