programming/알고리즘32 [백준, G3, 8972] 미친 아두이노 0. 문제 링크 https://www.acmicpc.net/problem/8972 8972번: 미친 아두이노 요즘 종수는 아두이노를 이용해 "Robots"이라는 게임을 만들었다. 종수는 아두이노 한대를 조정하며, 미친 아두이노를 피해다녀야 한다. 미친 아두이노는 종수의 아두이노를 향해 점점 다가온다. www.acmicpc.net 1. 문제 핵심 아래 조건을 순서대로 진행하며 종료되는 조건에 맞게 결과를 출력해주면 된다. 게임은 R×C크기의 보드 위에서 이루어지며, 아래와 같은 5가지 과정이 반복된다. 먼저, 종수가 아두이노를 8가지 방향(수직,수평,대각선)으로 이동시키거나, 그 위치에 그대로 놔둔다. 종수의 아두이노가 미친 아두이노가 있는 칸으로 이동한 경우에는 게임이 끝나게 되며, 종수는 게임을 지게 .. 2022. 12. 21. 뉴스 정하기 0. 문제 링크 https://www.acmicpc.net/problem/1135 1135번: 뉴스 전하기 민식이는 회사의 매니저이다. 그리고, 민식이는 회사의 중요한 뉴스를 모든 직원에게 빠르게 전달하려고 한다. 민식이의 회사는 트리 구조이다. 모든 직원은 정확하게 한 명의 직속 상사가 있다 www.acmicpc.net 1. 문제 핵심 민식이의 회사는 트리 구조이다. 모든 직원은 정확하게 한 명의 직속 상사가 있다. 자기자신은 그들 자기 자신의 직접 또는 간접 상사가 아니고, 모든 직원은 민식이의 직접 또는 간접적인 부하이다. 민식이는 일단 자기 자신의 직속 부하에게 한 번에 한 사람씩 전화를 한다. 뉴스를 들은 후에, 각 부하는 그의 직속 부하에게 한 번에 한 사람씩 전화를 한다. 이 것은 모든 직원.. 2022. 10. 30. [백준, G4, 1043] 거짓말 0. 문제 링크 https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 1. 문제 핵심 지민이는 거짓말쟁이로 알려지기는 싫어한다. 문제는 몇몇 사람들은 그 이야기의 진실을 안다는 것이다. 따라서 이런 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수 밖에 없다. 당연히, 어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다. 지민이는 이런 일을 모두 피해야 한다. 지민이는 모든 파티에.. 2022. 10. 29. [백준, G3, 2539] 모자이크 0. 문제 링크 https://www.acmicpc.net/problem/2539 2539번: 모자이크 수찬이는 선생님을 도와서 교실 벽면을 장식할 모자이크 그림을 그리기로 하였다. 이를 위하여 직사각형 모양의 큰 도화지를 준비하여 교실 벽에 붙이고 1cm 간격으로 가로선과 세로선을 그려서 www.acmicpc.net 1. 문제 핵심 사용되는 색종이는 모두 크기가 같고 정사각형 모양이다. 색종이 크기는 한 변의 길이로 나타내며, 원하는 크기의 색종이는 모두 구할 수 있다. 모든 색종이는 반드시 도화지의 밑변에 맞추어 붙인다. 이때 색종이를 겹쳐서 붙일 수 있다. 1, 2, 3번 조건의 설명은 조금 간단히 되어있어서 전 이런 식으로 이해를 했습니다. 1. 색종이는 도화지보다 커도 상관 없다. 2. 도화지보.. 2022. 10. 23. [백준, 15486, G5] 퇴사 2 0. 문제 링크 https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 1. 문제 핵심 퇴사일인 N+1일 전까지인 N일 동안 최대한 최대 수익이 가능한 상담일정을 잡는 것 한 상담을 맡게 되면 그 상담이 끝날 때까지 다른 상담은 받지 못함. 2. 문제 접근 DP문제이기 때문에 dp배열을 하나 만들어주었고 dp 배열은 그 날 최대로 벌 수 있는 비용을 저장합니다. 각 일자별에 종료되는 상담 일정을 저장하기 위해 Stack배.. 2022. 10. 20. [백준, 14719, G5] 빗물 0. 문제 링크 https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 1. 문제 핵심 블록에 의해 고이는 물의 총량을 구하는 문제 2. 문제 접근 가로, 세로 500개밖에 되지 않기 때문에 완전 탐색을 하면 된다고 생각했습니다. 가로 0부터 H-1까지 확인하며 첫 블록 이후로 그 다음 블록까지 빗물에 의해 고일 수 있는 양을 한 줄씩 계산해주고 한 줄이 끝나면 answer에 더해주었습니다. 3. 코드 분석 4. 베스트 코드 분석 5.. 2022. 10. 20. [백준, 1956, G4] 운동 0. 문제 링크 https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 1. 문제 핵심 일방 통행 도로로 이루어진 V개 마을과 E개 도로로 구성된 도시가 있다. 사이클이 형성된 최소 도로를 찾아야 한다. 2. 문제 접근 처음에는 MST로 간선치가 작은 선분부터 집어넣고 사이클이 형성되었으면 BFS로 최소 경로 비용을 찾기로 했습니다. 하지만 역시 시간 초과, 메모리 초과로 해결할 수 없었습니다. 질문 확인 결과 사이클.. 2022. 10. 20. [백준, 7662, G4] 이중 우선순위 큐 0. 문제 링크 https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 1. 문제 핵심 우선순위 큐인데 입력받은 값을 양쪽으로 제거할 수 있어야 합니다. 2. 문제 접근 자바의 PriorityQueue는 처음 선언할 때 comparator를 변경할 수 없기 때문에 PQ를 2개 만들던가, 아니면 다른 Collection을 사용해야 한다고 생각은 했습니다. 하지만 PQ를 2개 만들었을 때 가장 높은 데이터를 삭제했을 때 오름차순 PQ에 저장한 해당 데.. 2022. 10. 18. [백준, 13905, G4, MST] 세부 0. 문제 링크 https://www.acmicpc.net/problem/13905 13905번: 세부 첫 번째 줄에는 섬에 존재하는 집의 수 N(2≤N≤100,000)와 다리의 수 M(1≤M≤300,000)이 주어진다. 두 번째 줄에는 숭이의 출발 위치(s)와 혜빈이의 위치(e)가 주어진다. (1≤s, e≤N, s≠e). 다음 M개의 줄 www.acmicpc.net 1. 문제 핵심 그래프 탐색을 하며 출발지부터 목적지까지 경로를 탐색하는 중에 가장 빼빼로를 많이 들고갈 수 있는 경로를 탐색하는 문제입니다. 2. 문제 접근 그래프 탐색이기 때문에 별 생각없이 다익스트라를 사용했습니다. 다익스트라를 사용했을 때 가지치기를 적절히 사용해준다면 문제는 풀립니다. 하지만 자바 1등과 시간 차이가 커서 다른 방법.. 2022. 10. 18. [백준, S1, DP] 쉬운 계단 수 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; int N = Integer.parseInt(br.readLine()); int size = 0; if (N == 1) size = 3; else size = N + 1; long[][] dp = new long[N + 1][10]; for (int i = 1; i < 10; i++) { dp[1][i] = 1; } for (int.. 2022. 10. 18. 이전 1 2 3 4 다음
