본문 바로가기

소스코드

 (42)
[백준 / BOJ] 23247 Ten (Java) 문제 출처 : https://www.acmicpc.net/problem/23247 23247번: Ten Your program is to read from standard input. The input starts with two positive integers $m$ and $n$ ($1 \le m, n \le 300$), denoting the dimensions of the land, which are given separated by a space. Each of the following $m$ lines contains $n$ positive in www.acmicpc.net N*M그리드에서 A*B범위의 사각형을 만들때, 그 사각형 범위안에 포함된 원소의 합을 10으로 만드는 사각형 범위의 갯수..
[백준 / BOJ] 22866 탑 보기 문제 출처 : https://www.acmicpc.net/problem/22866 22866번: 탑 보기 3번째 건물에서 볼 수 있는 건물은 2, 4, 8번째 건물로 총 3개를 볼 수 있다. 그 중 3번째 건물과 가장 가까운 건물은 2, 4번째 있는 건물로 이 중 번호가 작은 번호인 2가 답이 된다. www.acmicpc.net 일직선으로 다양한 높이의 건물이 존재한다. 한 건물 i의 옥상에서 다른 건물들을 볼때 높이가 건물 i보다 큰 건물만 볼 수 있으며, 높이가 L인 건물 뒤에 L이하인 건물은 볼 수 없다고 할때, 각 건물에서 볼 수 있는 건물의 최대 수와 가장 가까운 건물의 idx를 구하는 문제다. 풀이 N이 최대 100,000으로 완전탐색으로 구현할 경우 O(N*N)번 반복해서 TLE를 맞게된다...
[백준 / BOJ] 1195 킥다운 문제 출처 : https://www.acmicpc.net/problem/1195 1195번: 킥다운 첫 줄에는 첫 번째 기어 파트를 나타내는 1과 2로 구성된 문자열이 주어진다. 두 번째 줄에는 마찬가지로 두 번째 기어 파트를 나타내는 1, 2로 구성된 문자열이 주어진다. 여기서 1은 홈을, 2는 www.acmicpc.net 두개의 기어파트가 주어진다. 각 기어파트는 1과 2로 이루어져있는데, 1은 '홈(들어가있는 부분)' 2는 '이(나와있는 부분)'를 나타낸다 이 때, 두개의 기어파트를 적절히 조합하여 조합된 기어파트의 길이의 최솟값을 구하는 문제다. 풀이 기어의 길이가 최대 100이므로 완전탐색으로 풀리는 문제다. 문제에서 주어진 그대로 구현하면 되는데, 몇가지 주의할 점 이 있다. - 기어가 맞물린..
[백준 / BOJ] 9489 사촌 문제 출처 : https://www.acmicpc.net/problem/9489 9489번: 사촌 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 노드의 수 n과 사촌의 수를 구해야 하는 노드의 번호 k가 주어진다. (1 ≤ n ≤ 1,000, 1 ≤ k ≤ 1,000,000) 다음 줄 www.acmicpc.net n명의 사람과 사촌의 수를 구해야하는 노드의 번호 k가 주어진다. 이때, k와 사촌인 사람의 수를 구하는 문제다. 풀이 (뜬금없는 메모리초과가 나온문제 자바로 풀어서 그런듯?) 트리 구조를 만들고 탐색을 해주면 풀리는 문제이다. 시간복잡도는, 1. 트리구조를 만드는데 n 2. 사촌을 찾는데 n 으로 O(2n)이 되는데, n이 최대 1000 이므로 TLE는 걱정..
[백준 / BOJ] 23040 누텔라 트리 (Easy) 문제 출처 : https://www.acmicpc.net/problem/23040 23040번: 누텔라 트리 (Easy) 첫째 줄에 트리의 정점의 개수 $N$이 주어진다. ($2 \le N \le 100\,000$) 이후 $(N-1)$개 줄에 걸쳐 각 간선이 잇는 두 정점의 번호 $u_i$, $v_i$가 공백을 사이에 두고 주어진다. ($1 \le u_i \le N$, $1 \le v_i \le N$, www.acmicpc.net 빨간색과 검은색 정점들로 이루어진 트리가 있다. 시작은 검은색 정점, 나머지 정점은 모두 빨간색인 경우 이를 누텔라 경로라고한다. 트리에서 누텔라 경로의 갯수를 찾는 문제였다. 풀이 시간초과를 주의해야했던 문제였다. 논리는 아래와 같다. 검은색 정점에서 시작해, 거쳐간 빨간색 ..
[백준 / BOJ] 17471 게리맨더링 문제 출처 : https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net N개의 선거구와 각 선거구에 사는 인원수가 주어진다. 선거구는 2개의 선거진영으로 나뉘며, 이때, 각 선거진영 선거진영 별로 모두 연결되어있어야한다. 이때, 선거진영의 인구수 차이를 최소화하는 값을 구하는 문제다. 풀이 비트마스킹을 이용한 완전탐색으로 푼 문제다. 처음엔 비트마스킹 + 백 트래킹으로 생각했으나, 이 방법으로는 모든 경우를 봐주지 못해서 풀기 힘들어 보였다. 알고리즘은 다음과 같다. 1. ..
[백준 / BOJ] 12904 A와 B 문제 출처 : https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 문자 'A'와 'B'가 주어진다. 두 문자를 아래와 같은 규칙으로 연결해 문자열 T를 만든다. 1. 문자열 뒤에 A를 붙인다. 2. 문자열 을 뒤집고 뒤에 B를 붙인다. 이때, 문자열 S를 이용해 문자열 T를 만들 수 있는지 알아내는 프로그램을 만드는 문제다. 풀이 아이디어 문제다. 문자열 S를 이용해 문자열 T를 만들려면, 매 선택마다 2가지 ..
[백준 / BOJ] 17363 우유가 넘어지면? 문제 출처 : https://www.acmicpc.net/problem/17363 17363번: 우유가 넘어지면? 첫 줄에 그림의 세로 길이와 가로 길이를 의미하는 정수 N과 M(1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에 걸쳐 그림의 각 줄을 의미하는 M글자의 문자열이 하나씩 주어진다. 문자열은 공백을 포 www.acmicpc.net 입력된 N*M배열을 왼쪽으로 90도 회전한 결과를 출력하는 문제다. 풀이 문제에서 하란대로 구현하면 되는 간단한 문제다. 입력받은 문자를 왼쪽으로 90도 회전한 값을 HashMap에 저장해 놓고 HashMap에 저장된 값과 매치해서 출력하면된다. 주요 소스코드 private void init(){ dic.put('.','.'); dic.put('O','O')..

티스토리툴바