본문 바로가기

알고리즘 (2020 : 08 : 10 ~ )

 (260)
[백준 / BOJ] 10885 수열의 장인 문제 출처 : https://www.acmicpc.net/problem/10885 10885번: 수열의 장인 승현이는 수열을 찾는 사람들을 위해 길이가 N 인 수열 a1, a2, ··· , aN을 만드는 일을 하고 있다. 승현이는 경력이 짧아서 각 원소가 -2 이상 2 이하의 정수인 수열만 만들 수 있고, 그래서인지 수 www.acmicpc.net 길이 N의 수열이 주어진다. 수열의 각 수는 -2, -1, 0, 1 2로 이루어져있으며, i번째 수열을 Ai, j번째 수열을 Bj라 하자. (i
[백준 / BOJ] 10881 프로도의 선물 포장 (Java) 문제 출처 : https://www.acmicpc.net/problem/10881 10881번: 프로도의 선물 포장 프로도는 네오에게 줄 생일 선물을 세 개 샀다. 이 세 개의 선물은 직사각형 모양의 선물 상자에 각각 하나씩 담겨 있다. 프로도는 이 선물들을 적당한 크기의 직사각형 포장 상자에 넣어 포장하 www.acmicpc.net 프로도는 네오에게 줄 생일 선물을 세 개 샀다. 선물 세 게를 N*M 크기의 상자에 적절히 담을려고한다. (모든 상자의 면은 서로 수평되어야 하며, 상자는 90도 회전가능하다.) 이때, 상자의 사이즈를 가장 작게하는 프로그램을 구하는 문제다. 풀이 상자가 최대 3개이고, 테스트케이스도 10,000이므로 완전탐색으로 풀수있는 문제다. 다만, 구현이 까다로웠는데, 상자의 크기가..
[백준 / BOJ] 1561 놀이 공원 문제 출처 : 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 놀이공원에 N명의 사람과, M개의 놀이기구가 있다. M개의 놀이기구는 각각 운행시간이 있으며, N명의 사람은 놀이기구를 "현재 탑승가능한 놀이기구중 빠른번호 순서"로 탑승하려고한다. 이때, 마지막사람이 탑승할 놀이기구의 번호를 출력하는 문제다. 풀이 처음 문제를 봤을때는, 스킵하는 방식의 dp를 이용한 문제일거라고 생각했는데, N이 최대 2,00..
[백준 / BOJ] 18430 무기 공학 (Java) 문제 출처 : https://www.acmicpc.net/problem/18430 18430번: 무기 공학 첫째 줄에는 길동이가 가지고 있는 나무 재료의 세로, 가로 크기를 의미하는 두 자연수 N, M이 주어진다. (1 ≤ N, M ≤ 5) 다음 N개의 줄에 걸쳐서, 매 줄마다 나무 재료의 각 위치의 강도를 나타내 www.acmicpc.net N*M그리드가 주어진다. 길동이는 N*M그리드의 각 칸을 적절히 잘라서 부메랑을 만들어야한다. 길동이가 만들수있는 부메랑들의 크기의 총합을 가장 크게하는 프로그램을 만드는 문제다. 풀이 N과 M이 5가 최대이므로 완전탐색으로 풀수있는 문제였다. 백 트래킹으로 구현한 전형적인 백트래킹 문제다. 구현중 주의할점은 아래와 같다. 현재 위치를 y,x라 했을때, 다음에 탐색..
[백준 / BOJ] 1244 스위치 켜고 끄기 문제 출처 : https://www.acmicpc.net/problem/1244 1244번: 스위치 켜고 끄기 첫째 줄에는 스위치 개수가 주어진다. 스위치 개수는 100 이하인 양의 정수이다. 둘째 줄에는 각 스위치의 상태가 주어진다. 켜져 있으면 1, 꺼져있으면 0이라고 표시하고 사이에 빈칸이 하나씩 www.acmicpc.net 1번부터 N번까지 총 N개의 스위치가 있다. 쿼리가 주어졌을때, 최종 스위치 상태를 출력하는 문제다. 문제에서 주어진 그대로 구현하면 되는문제다. 출력이 20이 넘어갈때, 줄 바꿈을 해줘야하는점만 주의하면 어렵지않게 풀리는 문제였다. 주요 소스코드 private void girl(int num){ int left = num; int right = num; while(left >..
[백준 / BOJ] 1765 닭싸움 팀 정하기 (Java) 문제 출처 : https://www.acmicpc.net/problem/1765 1765번: 닭싸움 팀 정하기 1번 학생 혼자 팀, 2, 4, 6번 학생 셋이서 팀, 3, 5번 학생 둘이서 팀일 때, 팀의 개수가 최대이다. www.acmicpc.net n명의 학생, m개의 학생들 사이의 관계가 주어졌을때, n명의 학생들로 최대 몇개의 팀을 만들수있는지 알아내는 프로그램을 만드는 문제다. 풀이 문제 해석이 정말 어려운 문제였다. 문제에서 인간관계를 다음과 같이 정리할 수 있다고 한다. 내 친구의 친구는 내 친구이다. 내 원수의 원수도 내 친구이다. 처음에 이걸보고 가능한 인간관계 경우의 수를 다음과 같이 생각했다.(재귀적으로) 내 친구의 친구는 내 친구이다. 내 친구의 원수의 원수는 내 친구이다. 내 친구..
[백준 / BOJ] 13335 트럭 (Java) 문제 출처 : https://www.acmicpc.net/problem/13335 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net n개의 트럭이 길이 w인 다리를 지나야한다. 다리가 견딜수있는 최대 무게가 L이라할때, n개의 트럭이 모두 지나기 위해서 걸리는 시간을 구하는 문제다. 풀이 구현 문제였다. 로직은 아래와 같다. 1. 다리의 현재 상태를 저장하는 큐를 하나 만든다. 이 큐에는 트럭이 다리에 진입한 시간, 무게가 저장될것이다. 2. 다리가 새로운 트럭을 ..
[백준 / BOJ] 9375 패션왕 신해빈 (Java) 문제 출처 : https://www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 해빈이는 N개의 옷을 갖고있다. 패션에 매우 민감한 해빈이는 날마다 다른조합의 옷을 입어야한다. 이때, 해빈이가 옷을 조합이 겹치지않게 입을수있는 최대 날짜를 계산하는 문제다. 풀이 솔브드 난이도가 실4로 되어있길래, 생각없이 백트래킹으로 풀었는데, 시간초과가 났다. N이 최대 30이므로 모..

티스토리툴바