본문 바로가기

분류 전체보기

 (340)
[백준 / BOJ] 15970 화살표 그리기 문제 출처 : www.acmicpc.net/problem/15970 15970번: 화살표 그리기 직선 위에 위치를 나타내는 0, 1, 2, ...와 같은 음수가 아닌 정수들이 일정한 간격으로 오른쪽 방향으로 놓여 있다. 이러한 위치들 중 N개의 위치에 하나씩 점들이 주어진다(). 주어진 점들 www.acmicpc.net 점들의 색깔과 위치(x좌표)가 주어진다. 각각의 점을 가까우면서 같은색깔인 점에 연결할려할때, 연결한 선의 최대거리를 구하는 문제다. 풀이 N이 크지않아 완전탐색으로도 풀리는문제다. 문제를 잘 읽지않고 점들의 색깔이 항상 2개인줄 알고풀다가 몇번 틀렸었다. 1. 점들을 입력받을때, 같은 색깔은 같은 벡터에 들어가도록 입력받는다. 2. 각 벡터를 N번 정렬한다. 3. 현재 점의 idx에서 ..
[백준 / BOJ] 8982 수족관 1 문제 출처 : www.acmicpc.net/problem/8982 8982번: 수족관 1 입력의 첫 줄은 수족관의 경계에 있는 꼭짓점의 개수 N(1 ≤ N ≤ 5,000)이 주어진다. N은 짝수이다. 수족관의 경계는 항상 꼭짓점 (0, 0)부터 시작한다. 그리고 마지막 꼭짓점은 (A, 0)의 형태로 끝난 www.acmicpc.net 물이 들어있는 수족관이있다. 수족관의 바닥에 구멍이 뚫려있을때, 각 구멍을통해 빠져나간후 남은 물의 양을 구하는 문제다. 풀이 범위가 크지않아 완전탐색으로도 풀리는 문제다. 각 구멍의 좌표를 기준으로 왼쪽, 오른쪽으로 탐색하며 현재의 높이보다 수족관의 바닥의 높이가 높을경우, 높이를 올려주며 남아있는 물의 양을 구해주면된다. 1. 구멍이 있는 바닥의 x1(시작 x 좌표) 부터..
[백준 / BOJ] 2495 연속구간 문제 출처 : www.acmicpc.net/problem/2495 2495번: 연속구간 여덟 자리의 양의 정수가 주어질 때, 그 안에서 연속하여 같은 숫자가 나오는 것이 없으면 1을 출력하고, 있으면 같은 숫자가 연속해서 나오는 구간 중 가장 긴 것의 길이를 출력하는 프로그램을 www.acmicpc.net 여덟자리 정수가 주어졌을때, 연속해서 나오는 정수들의 최대 갯수를 구하면된다. 풀이 입력받고 연속해서 나오는 정수들의 최대갯수를 구하면 된다. 정수로 입력받고 한자리씩 짤라가며 해도 되지만, String을 사용하면 훨씬 편하게 할수있다. 소스코드 https://github.com/devxb/JJUNalgo/blob/master/2495%20%EC%97%B0%EC%86%8D%EA%B5%AC%EA%B0%8..
[백준 / BOJ] 1516 게임 개발 문제 출처 : www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net N개의 건물이 주어지고, 각 건물을 짓는 시간과 그 건물을 짓기위해 먼저 지어야할 건물들이 주어진다. 이때 각 건물을 짓기 위해 필요한 최소 시간을 구하는 문제다. (각 건물은 동시에 지을수있다.) 풀이 N의 최댓값이 500이라 완전탐색을 하게되면, 최악의경우 501^2*250 만큼 돌아서 시간초과가 난다. DP로 풀리는 문제였다. 각 건물을 짓기위해 지어야할 선행건물들을 모두 지었다면..
[백준 / BOJ] 1082 방 번호 문제 출처 : www.acmicpc.net/problem/1082 1082번: 방 번호 문방구에서 파는 숫자의 개수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 문방구에서 파는 숫자는 0보다 크거나 같고, N-1보다 작거나 같은 자연수이다. 예를 들어, N=4이면, 문방구에서 파 www.acmicpc.net 갖고있는돈이 주어지고, 각 숫자들의 가격이주어진다 (0~9번까지숫자들의 가격) 이때, 숫자들을 조합해서만들수있는 최댓값을 찾는 문제다. 예를들어, 예제 1의경우, 순서대로 숫자 2를 8원에사고 숫자 1을 7원에 , 숫자 0을 6원에사면, 총 21원으로 210이 만들어지고 이때 최댓값을 갖는다. 풀이 완전탐색으로 풀경우, 최악의 경우, 총 10개의 글자가 중복을 허용해서 50개의 자리에 올수..
[백준 / BOJ] 1083 소트 문제 출처 : www.acmicpc.net/problem/1083 1083번: 소트 크기가 N인 배열 A가 있다. 배열에 있는 모든 수는 서로 다르다. 이 배열을 소트할 때, 연속된 두 개의 원소만 교환할 수 있다. 그리고, 교환은 많아봐야 S번 할 수 있다. 이때, 소트한 결과가 사전 www.acmicpc.net N크기의 정수배열과 S가 주어졌을때, 정수들의 순서를 최대 S번 바꿔서 사전순으로 가장 뒤에있는 것을 출력하는 문제다. 예를들어, 5 10 20 30 40 50 5 는 50 20 10 30 40 이 출력되어야한다. 풀이 그리디로 풀리는 문제였다. 사전순으로 가장 뒤에있는단어는 1. 앞에있는 단어가 뒤에있는 단어보다 클수록 사전순으로 앞선다. 이런 조건이있다. 따라서, 현재 위치에서 S번 뒤로 ..
[백준 / BOJ] 19591 독특한 계산기 문제 출처 : www.acmicpc.net/problem/19591 19591번: 독특한 계산기 숫자, '+', '*', '-', '/'로만 이루어진 길이가 106 이하인 수식이 주어진다. 계산 과정 중의 모든 수는 −263 이상 263 미만이며, 0으로 나누는 경우는 없다. 숫자 앞에 불필요한 0이 있을 수 있다. www.acmicpc.net 수식이 주어졌을때, 계산을 하는 문제다. 계산을 할때 규칙이 있는데, 가장 앞, 혹은 가장뒤에있는 것만 계산할수있다. 이때, 곱하기 나누기를 더하기 빼기보다 먼저 계산하고, 수식 우선순위가 같다면 계산결과가 큰것부터 계산한다. 풀이 문제에서 하란대로만 구현하면 풀리는문제다. deq자료구조를 이용했다. 숫자을 저장하는 deq, 연산자를 저장하는 deq을 각각 만들고..
[백준 / BOJ] 1005 ACM Craft 문제 출처 : www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 내가 원하는 건물을 건설할때 걸리는 최소 시간을 출력하는 문제다. 풀이 완전탐색으로 풀경우 N 3 이렇게 저장이 될건데, 4번건물을 짓기위해선 4번에 연결된 건물들을 모두 지어야한다(2번과 3번)라는 뜻 2. 끝까지 탐색하며 건물을 지을때마다 check배열을 업데이트 해준다. (바텀업으로 구현함) check배열을 업데이트할때, 전 위치의 건물들중 최댓값을 뽑아서 업데이트 해줘야함 이때 이미 ..

티스토리툴바