본문 바로가기

BOJ58

[BOJ][Java] 백준 2109번: 순회강연 문제 설명 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. 각 대학에서 제시하는 d와 p값은 서로 다를 수도 있다. 이 학자는 이를 바탕으로, 가장 많은 돈을 벌 수 있도록 순회강연을 하려 한다. 강연의 특성상, 이 학자는 하루에 최대 한 곳에서만 강연을 할 수 있다. 예를 들어 네 대학에서 제시한 p값이 각각 50, 10, 20, 30이고, d값이 차례로 2, 1, 2, 1 이라고 하자. 이럴 때에는 첫째 날에 4번 대학에서 강연을 하고, 둘째 날에 1번 대학에서 강연을 하면 80만큼의 돈을 벌 수 있다. 문제 풀이 이 .. 2022. 3. 6.
[BOJ][Java] 백준 2138번: 전구와 스위치 문제 설명 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 있는 전구는 켜지고, 켜져 있는 전구는 꺼지게 된다. 1번 스위치를 눌렀을 경우에는 1, 2번 전구의 상태가 바뀌고, N번 스위치를 눌렀을 경우에는 N-1, N번 전구의 상태가 바뀐다. N개의 전구들의 현재 상태와 우리가 만들고자 하는 상태가 주어졌을 때, 그 상태를 만들기 위해 스위치를 최소 몇 번 누르면 되는지 알아내는 프로그램을 작성하시오. 문제 풀이 이 문제의 핵심은1. 첫 번째 전구가 켜져있는지, 꺼져있는지 경우를 나누는 것2. i를 기준으로 i-1번째가 만들고자 하는.. 2022. 3. 6.
[BOJ][Java] 백준 1976번: 여행 가자 문제 설명 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 수 있다. 도시들의 개수와 도시들 간의 연결 여부가 주어져 있고, 동혁이의 여행 계획에 속한 도시들이 순서대로 주어졌을 때 가능한지 여부를 판별하는 프로그램을 작성하시오. 같은 도시를 여러 번 방문하는 것도 가능하다. 제한조건 첫 줄에 도시의.. 2022. 3. 4.
[BOJ][Java] 백준 1080번: 행렬 문제 설명 0과 1로만 이루어진 행렬 A와 행렬 B가 있다. 이때, 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을 구하는 프로그램을 작성하시오. 행렬을 변환하는 연산은 어떤 3×3크기의 부분 행렬에 있는 모든 원소를 뒤집는 것이다. (0 → 1, 1 → 0) 문제 풀이 저는 처음 이 문제를 고민할 때 제일 최적화된 답을 어떻게 찾을까? 제일 겹치는 범위가 큰 곳을 찾아서 뒤집어야할까? 라는 고민이였습니다. 하지만 위의 방법처럼 코드를 구현하면 적절한 위치를 찾는데에 시간이 소요되기 때문에 좋지 않은 코드가 됩니다. 그렇다면 어떻게 해야할까요? 방법은 단순합니다. 3x3 범위를 비교하면서 하나라도 다른 곳이 있으면 뒤집는 것입니다. 이것때문에 이 문제가 그리디 알고리즘이 아닌가 싶습니다. 만.. 2022. 3. 4.
[BOJ][Java] 백준 1783번: 병든 나이트 문제 설명 병든 나이트가 N × M 크기 체스판의 가장 왼쪽아래 칸에 위치해 있다. 병든 나이트는 건강한 보통 체스의 나이트와 다르게 4가지로만 움직일 수 있다. 2칸 위로, 1칸 오른쪽 1칸 위로, 2칸 오른쪽 1칸 아래로, 2칸 오른쪽 2칸 아래로, 1칸 오른쪽 병든 나이트는 여행을 시작하려고 하고, 여행을 하면서 방문한 칸의 수를 최대로 하려고 한다. 병든 나이트의 이동 횟수가 4번보다 적지 않다면, 이동 방법을 모두 한 번씩 사용해야 한다. 이동 횟수가 4번보다 적은 경우(방문한 칸이 5개 미만)에는 이동 방법에 대한 제약이 없다. 체스판의 크기가 주어졌을 때, 병든 나이트가 여행에서 방문할 수 있는 칸의 최대 개수를 구해보자. 문제 풀이 이 문제의 핵심은 오른쪽으로만 이동하는 것과 이동 횟수가 .. 2022. 3. 4.
[BOJ] 백준 20364번: 부동산 다툼 문제 설명 이진 트리 모양의 땅으로 이루어진 꽉꽉마을에는 오리들이 살고 있다. 땅 번호는 다음과 같이 매겨진다. 루트 땅의 번호는 1이다. 어떤 땅의 번호가 K라면, 왼쪽 자식 땅의 번호는 2 × K, 오른쪽 자식 땅의 번호는 2 × K + 1이다. 어느날 오리들끼리 부동산 다툼이 일어나서 꽉꽉마을 촌장 경완이가 해결책을 가져왔고, 그 내용은 다음과 같다. 오리들을 한 줄로 대기시킨다. 맨 처음 오리들은 1번 땅에 위치해 있다. 오리들이 서있는 순서대로 원하는 땅을 가지도록 한다. 만약, 한 오리가 원하는 땅까지 가는 길에 이미 다른 오리가 점유한 땅이 있다면 막대한 세금을 내야 하는 이유로 해당 땅을 지나가지 못해 그 오리는 땅을 가지지 못한다. 오리가 원하는 땅까지 가는 길에는 오리가 원하는 땅도 포.. 2022. 2. 6.
[BOJ] 백준 10926번: ??! 문제 설명 준하는 사이트에 회원가입을 하다가 joonas라는 아이디가 이미 존재하는 것을 보고 놀랐다. 준하는 놀람을 ??!로 표현한다. 준하가 가입하려고 하는 사이트에 이미 존재하는 아이디가 주어졌을 때, 놀람을 표현하는 프로그램을 작성하시오. 문제 풀이 입력받은 문자엘에 "??!"만 붙여주면 되는 문제입니다. 풀이 코드 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.println(sc.next()+"??!"); } } https://www.acmicpc.net/problem/10926 2022. 1. 29.
[BOJ] 백준 11819번: The Shortest does not Mean the Simplest 문제 Your are given integer numbers A, B and C. Output the remainder of division AB (B-th power of A) by C . 입력 The only line of the input file contains three integers: A, B, C (1 ≤ A,B,C ≤ 1018). Numbers are separated by spaces. 풀이 이 문제는 반복문을 통해 해결하려고 하면 B의 범위가 10^18까지 때문에 시간초과가 나게 됩니다. 따라서 분할정복을 통해 접근해야합니다. 처음에 10^18범위인 것을 보고 long으로 잡고 해결하려고 시도했으나 중간중간 rest*rest%C*(A%C)라는 조건에서 long의 범위를 벗어나는 것이 .. 2022. 1. 22.
[BOJ] 백준 9019번: DSLR 문제 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 저장된 n을 다음과 같이 변환한다. n의 네 자릿수를 d1, d2, d3, d4라고 하자(즉 n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4라고 하자) D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다. 그 결과 값(2n mod 10000)을 레지스터에 저장한다. S: S 는 n에서 1 을 뺀 결과 n-1을 레지스터에 저장한다. n이 0 이라면 9999 가 대신 레지스터에 저장된다. L: L 은 n의 각 자릿.. 2022. 1. 18.

티스토리툴바