본문 바로가기

Algorithm/BaekJoon

 (7)
[백준/구간 합] 10986 나머지 합 구하기 풀이 (JAVA) 문제 주소 https://www.acmicpc.net/problem/10986 유형 구간 합 풀이 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.HashMap; import java.util.HashSet; import java.util.StringTokenizer; public class Main { public static void main(String args[]) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringT..
[그리디/우선순위 큐] 백준 11000 강의실 배정 풀이 [백준] Gold5 - 강의실 배정_11000 문제 https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 풀이 방법 이거 푸는데 최소 3시간 이상은 잡힌 것 같다.. 처음에 문제를 잘못보고 강의를 최대한 많이 듣는 횟수를 알아내라는 것인줄 알았는데, 계속 틀려서 다시 읽어보니 최소한의 강의실 갯수를 구하는 문제였다. 처음에 잘못된 접근법은 회의실 배정 문제처럼 종료시간을 기준으로 오름차순으로 정렬후 풀었으나, 이러면 값은 안구해진다. 시작시간으로 정렬 후 PriorityQueue를 사용해서 최소 ..
[BFS/구현] 백준 16236 아기상어 풀이 문제 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 난이도 Gold 3 풀이 1. 아기상어 객체를 담은 클래스를 선언했다. 이 클래스는 현재 위치(a,b), 현재 크기(size), 현재 이동거리(distance). cnt(먹은 물고기 갯수)를 담고있고, eatShark() 메서드는 물고기를 먹을때, 먹은 물고기 갯수를 비교해 자신의 사이즈와 동일한 물고기를 먹으면 사이즈 업 하는 메서드이다. 2. 아기상어가 먹을 수 있는 물고기의 위치..
[백트래킹/BFS/완탐] 백준 14502번 연구소 풀이 문제 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이 1. 백트래킹을 이용하여 promising() (상,하,좌,우 또는 대각선에 벽 또는 바이러스가 있는지 검사하는 함수)가 true로 반환되면 벽(1)을 세우고 벽이 3개 세워질때까지 반복한다. 2. 벽이 3개 세워지면 bfs() 함수를 통해 바이러스 침투 경로를 확인하고, 안전한 공간의 갯수를 카운트 센 다음, max값이랑 비교 후 max값 대체 소스코드 import java.io.BufferedR..
[완전탐색] 백준 1051 숫자 정사각형 풀이 문제 N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 또는 열에 평행해야 한다. 입력 첫째 줄에 N과 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 수가 주어진다. 출력 첫째 줄에 정답 정사각형의 크기를 출력한다. 풀이 1. (a, b) 좌표 정보를 담고 있는 Node 클래스를 생성한다. 2. 입력받은 배열의 가로길이와 세로길이중 더 작은 것을 min에 저장한다. 3. process 함수를 통해서 재귀를 실시한다. 4. size (정사각형 크기)가 min이랑 같을 경우 종료한다. 5. 만약 4개의 꼭짓점의 값이 같다면 값을 ..
[BFS] 백준 1012 유기농 배추 풀이 문제 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다. 한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군..
[재귀] 백준 2331 반복수열 풀이 문제 다음과 같이 정의된 수열이 있다. D[1] = A D[n] = D[n-1]의 각 자리의 숫자를 P번 곱한 수들의 합 예를 들어 A=57, P=2일 때, 수열 D는 [57, 74(=52+72=25+49), 65, 61, 37, 58, 89, 145, 42, 20, 4, 16, 37, …]이 된다. 그 뒤에는 앞서 나온 수들(57부터가 아니라 58부터)이 반복된다. 이와 같은 수열을 계속 구하다 보면 언젠가 이와 같은 반복수열이 된다. 이때, 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 구하는 프로그램을 작성하시오. 위의 예에서는 [57, 74, 65, 61]의 네 개의 수가 남게 된다. 입력 첫째 줄에 A(1 ≤ A ≤ 9999), P(1 ≤ P ≤ 5)가 주어진다. 출력 첫째 줄에..

티스토리툴바