본문 바로가기

분류 전체보기

 (341)
[백준 / 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이므로 모..
[백준 / 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이므로, 완탐으로 풀경우 시간초과가 발생한다. 문제의 조건중 "레이저는 처음 만나는 탑만 수..

티스토리툴바