본문 바로가기

Algorithm

 (41)
[Java] BOJ14890_경사로 www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 행과 열을 구분하여 경사로를 놓아 지나갈 수 있는 길의 수를 셌다. 반복문을 진행하면서 평평한 부분의 길이를 세어주고 높이가 1 차이나는 오르막이 나올 경우 평평했던 부분이 놓을 수 있는 경사로보다 길다면 지나갈 수 있다고 판단해준다. 높이가 1 차이나는 내리막이 나올 경우 내리막이 나온 지점부터 평평한 부분의 길이를 세어주어 경사로를 놓을 수 있는지 판단한다. import java.io.*; import java.util.Strin..
[Java] BOJ14888_연산자 끼워넣기 www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 연산자를 순서에 상관있게 숫자 사이에 끼워 넣고 식을 계산하여 최댓값과 최솟값을 구하는 문제이다. '-', '/' 연산 등이 존재하여 가지치기를 할 수 없는 문제이다. 연산자를 순서에 맞도록 쉽게 사용하기 위해 oper배열을 만들어주고 연산자 수만큼 순서대로 담아주었다. +는 0, -는 1, *는 2, /는 3이라 할 때 예제 3같은 경우 oper배열에 [..
[Java] BOJ1475_방 번호 www.acmicpc.net/problem/1475 1475번: 방 번호 첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 구현 문제이다. "(6은 9를 뒤집어서 이용할 수 있고, 9는 6을 뒤집어서 이용할 수 있다.)"의 조건에 의해 6과 9를 같은 숫자로 생각할 수 있다. 배열 arr은 해당 인덱스의 숫자를 사용하기 위한 세트의 수를 담고 있다. 6과 9를 제외한 다른 수는 하나의 수를 표현하기 위해 하나의 세트가 필요하다. 6과 9는 같은 숫자로 생각하기로 했으므로 9가 나올 경우 index 6에 담아준다. 6은 2개를 하나의 세트로 표현할 수 있으므로 최종적으로 값을 2로 나눠준다. 배열을 정렬하여 가장 많은 세트..
[Java] BOJ14503_로봇 청소기 www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 문제에 주어진 조건대로 구현하는 시뮬레이션 문제이다. d라는 방향 값을 가지고 왼쪽 방향이 벽(값이 1)이거나 청소(값이 2)를 이미 했다면 방향을 회전시켜주고 방향을 몇 번 회전시켜주는지 나타내 주는 cnt를 증가시킨다. cnt가 4가 될 경우 네방향 모두 벽이거나 청소를 했다는 것이기 때문에 후진을 할 수 있는지 판단한다. 후진 방향이 벽이면 반복문을 빠져나오고 그렇지 않은 경우 cnt를 0으로 초기화해주..
[Java] BOJ14502_연구소 www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 특별한 알고리즘으로 벽을 최적의 위치에 놓을 방법이 없기 때문에 브루트 포스로 벽을 다 세워봐야 한다. 지도의 최대 크기가 64이고 벽은 3개밖에 세우지 않으므로 충분히 시간 안에 가능하다. 값이 0인(빈 칸)곳의 위치를 리스트에 담아두고 조합을 이용하여 3개씩 뽑아냈다. 해당 위치에 벽을 세운 임시 배열을 만들고 값이 2인(바이러스) 위치에서 BFS를 통해 바이러스를 퍼뜨렸다. 바이러스를 다 퍼뜨리고 0의 갯수를 세서 최..
[Java] BOJ14500_테트로미노 www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 각 칸에 가능한 테트로미노의 모양을 다 놓아보고 최댓값을 찾는 문제이다. i 행 j 열이 노란색칸일 때 가능한 테트로미노 모양은 위와 같이 19가지가 나오며 이 모양들 중 배열의 범위를 벗어나지 않는 모양들을 놓아보고 각 칸의 합을 구해 최댓값을 구한다. import java.io.*; import java.util.StringTokenizer; public class Main { static int N, M;..
[Java] BOJ1421_나무꾼 이다솜 www.acmicpc.net/problem/1421 1421번: 나무꾼 이다솜 첫째 줄에 이다솜이 가지고 있는 나무의 개수 N과 나무를 자를 때 드는 비용 C와 나무 한 단위의 가격 W이 주어진다. 둘째 줄부터 총 N개의 줄에 이다솜이 가지고 잇는 나무의 길이가 한 줄에 하나 www.acmicpc.net 1부터 가장 긴 나무의 길이까지 모든 나무를 잘라봐야 한다. 이때 자르는 길이보다 짧은 나무는 자를 수 없다. 자를 수 있는 모든 나무에 대해 K * L * W - (C * 자른 횟수)를 구해서 합해준 후 최댓값 비교를 한다. 여기서 주의할 점은 K * L * W - (C * 자른 횟수) 값이 음수가 나와서 합해줄 때 손해인 경우는 합하지 않아야한다. 위 처리를 안 해줄 경우 자르는 비용이 터무니없이 클..
[Java] BOJ13458_시험 감독 www.acmicpc.net/problem/13458 13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net 단순 구현문제이다. "각각의 시험장에 총감독관은 오직 1명만 있어야 하고, 부감독관은 여러 명 있어도 된다." 이 부분에서 총 감독관이 반드시 1명 있어야한다는 뜻이 없지만 예제의 출력을 봤을 때 반드시 1명 있어야하는 것을 알 수 있었다. 따라서 시험장 인원이 총감독관 한명으로 다 감독 가능하면 결과를 1 증가시켜줬고 그 경우가 아닐 때는 총감독관이 감..

티스토리툴바