본문 바로가기

소스코드

 (42)
[백준 / 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이므로 모..
[백준 / BOJ] 17182 우주 탐사선 (완전탐색) 문제 출처 : https://www.acmicpc.net/problem/17182 17182번: 우주 탐사선 우주 탐사선 ana호는 어떤 행성계를 탐사하기 위해 발사된다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하려 한다. 입력으로는 ana호가 탐색할 행성의 개수와 ana호가 발사되는 행성의 위 www.acmicpc.net 우주탐사선 ans호가 있다. ans호는 N개의 행성을 모두 탐사하는데 걸리는 최소시간을 계산하려한다. N개의 행성끼리 이동하는데 걸리는 시간이 주어질때 모든 행성을 탐사하기 위한 최소 시간을 출력하는 문제다. 풀이 플로이드 와샬로 최단경로를 만들어주고, 비트마스킹을 이용한 완전탐색으로 답을 찾은 문제다. (거의 3달만의 플로이드 와샬이라 알고리즘조차 가물 가물했다..) N이 최..
[백준 / BOJ] 17298 오큰수 (Java) 문제 출처 : https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net N개의 수로 이루어진 수열이 있다. 이 수열의 i번째 원소를 Ni라 할때, Ni보다 오른쪽에 있으면서 Ni보다 큰 수를 찾아서 구하는 프로그램을 만드는 문제다. 풀이 스택으로 푸는 문제다. 수열에서 Ni보다 오른쪽에 있는 수중 더 큰수를 찾아야한다. 즉, 입력받는 Ni을 스택에 계속 집어넣으면서, Stack의 가장 위에있는 원소가 입력받은 Ni보다 더 큰 경우 스택의 가장 위에있는 원소가 Ni..
[백준 / BOJ] 19644 좀비 떼가 기관총 진지에도 오다니 문제 출처 : https://www.acmicpc.net/problem/19644 19644번: 좀비 떼가 기관총 진지에도 오다니 킬로와 헥토는 좀비 떼로부터 탄약고를 사수하는 데에 성공했다. 포상 휴가나 조기 전역을 기대했으나 좀비 사태로 인해 계엄령이 선포되면서 오히려 전역이 연기되고 기관총 진지에 배치되었 www.acmicpc.net 기관총 진지에 좀비떼가 다가오고 있다. 킬로와 헥토는 기관총과 지뢰를 이용해 좀비를 막아야한다. 기관총은, L의 사거리에 있는 좀비를 모두 K데미지로 공격한다. 지뢰는 1M사거리에 있는 좀비를 제압한다. 이때, 킬로와 헥토가 좀비 떼에게서 살아남을수있을지 구하는 문제다. 풀이 그리디, 투포인터 문제였다. 좀비의 수(진지의 거리)와 유효사거리가 3*10^6 이므로 시뮬레..
[백준 / BOJ] 2493 탑 (Java) 문제 출처 : https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 서로 다른 높이를 갖고있는 N개의 탑이 있다. 이 탑을 일렬로 세우고 탑의 꼭대기에서 왼쪽으로 레이저를 발사한다. 이때, 레이저는 처음 만나는 탑만 수신할수있다. 각 탑에서 레이저를 발사할때, 각 탑별로 레이저를 수신하는 타워를 출력하는 문제다. 풀이 스택으로 푼 문제다. N이 500,000이므로, 완탐으로 풀경우 시간초과가 발생한다. 문제의 조건중 "레이저는 처음 만나는 탑만 수..
[백준 / BOJ] 3015 오아시스 재결합 문제 출처 : https://www.acmicpc.net/problem/3015 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net N명의 사람이 한 줄로 기다리고있다. i번째 사람과 i+a번째 사람이 서로 보기위해선, i ~ i+a사이에 i와 i+a보다 큰 사람이 없어야한다. 이때, 서로 볼수있는 사람의 쌍을 구하는 문제다. 풀이 푸는데 시간이 좀 많이 걸린문제다. 처음엔, 세그먼트 트리로 생각했으나, N*N/2 시간이 걸릴것이라 생각하여 포기했다.(문제 질문을 보니 세그먼트로도 풀리는듯..

티스토리툴바