본문 바로가기

코테

 (13)
[백준 / BOJ] 12101 1, 2, 3 더하기 2 (cpp) 문제 출처 : https://www.acmicpc.net/problem/12101 12101번: 1, 2, 3 더하기 2 n을 1, 2, 3의 합으로 나타내는 방법 중에서 사전 순으로 k번째에 오는 것을 출력한다. k번째 오는 식이 없는 경우에는 -1을 출력한다. www.acmicpc.net 만들려는 숫자 n이 주어졌을때, n을 1,2,3을 이용해서 만들고 n을 만드는 경우의 수의 조합중 k번째를 찾아 출력하는 문제이다. 풀이 이런 유형의 DP를 풀어본적이 있어서 DP라고 착각했지만, n의 최댓값이 11로 작아서 완전탐색으로도 풀리는 문제다. 로직은 간단한데, 재귀를 이용해서 1,2,3으로 숫자 n을 만드는 모든 경우의 수를 저장해놓은다음 정렬 후 출력하면 된다. 주요 소스코드 void getComb(i..
[백준 / BOJ] 6209 제자리 멀리뛰기 문제 출처 : https://www.acmicpc.net/problem/6209 6209번: 제자리 멀리뛰기 첫 번째 줄에는 갇힌 돌섬으로부터 탈출구까지의 거리 d(1 ≤ d ≤ 1,000,000,000), 작은 돌섬의 수 n(0 ≤ n ≤ 50,000), 제거할 수 있는 작은 돌섬의 수 m (0 ≤ m ≤ n)이 공백으로 구분되어 주어진다. 두 www.acmicpc.net 시작지점(0번)에서 각각 일정 거리 떨어진 n개의 돌섬이 있다. 이때, n개의 돌섬중 m개를 제거하여 돌섬사이의 거리의 최솟값을 최대로 하는 문제이다. 풀이 문제에 나와있는 "최솟값을 최대"로 라는 키워드가 결정문제임을 알려주니 문제의 입력조건을 살펴보고 결정문제로 풀린다면 풀면 된다. 못 푼다면 DP로 풀면된다(모든 결정문제는 DP..
[백준 / BOJ] 2812 크게 만들기 (Java / 세그먼트 트리) 문제 출처 : https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net N자리의 수가 주어지며 이 수에서 K개의 숫자를 제거했을때 얻는 가장 큰 수를 구하는 문제이다. 풀이 세그먼트 트리로 푼 문제다. 문제를 N자리의 수에서 (N-K)개의 숫자를 선택하는 문제로 바꾼다면, 현재 선택가능한 범위 (left ~ right)에서 (N-K)번 숫자를 뽑아 최댓값을 만드는 문제로 바뀌게 된다. 이때, left ~ right의 범위는 최대 250,000만큼 차이가 날 수 있으므로, 완전탐색으로 현재 범위에서 최댓값을 찾는다면, (250,00..
[백준 / BOJ] 18809 Gaaaaaaaaaarden (Java) 문제 출처 : https://www.acmicpc.net/problem/18809 18809번: Gaaaaaaaaaarden 첫째 줄에 정원의 행의 개수와 열의 개수를 나타내는 N(2 ≤ N ≤ 50)과 M(2 ≤ M ≤ 50), 그리고 초록색 배양액의 개수 G(1 ≤ G ≤ 5)와 빨간색 배양액의 개수 R(1 ≤ R ≤ 5)이 한 칸의 빈칸을 사이에 두 www.acmicpc.net N*M크기의 정원에 빨간색 배양액 R개 초록색 배양액 G개를 뿌린다. 배양액을 뿌릴 수 있는 위치는 R+G곳 이며, 배양액을 뿌린 위치는 매 초마다 인접한 영역으로 퍼져나간다. 서로 다른 색의 배양액이 동시에 만나면 꽃이 피며, 배양액은 사라진다. 이때, 피울 수 있는 최대 꽃의 개수를 구하는 문제다 풀이 조합과 BFS로 풀..
[programmers/kakao] [3차] 압축 (Java/Trie) 문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/17684 코딩테스트 연습 - [3차] 압축 TOBEORNOTTOBEORTOBEORNOT [20, 15, 2, 5, 15, 18, 14, 15, 20, 27, 29, 31, 36, 30, 32, 34] programmers.co.kr 알파벳 'A' - 'Z'로 이루어진 사전과 문자열 msg가 주어진다. 이 msg의 문자중 사전과 최장 일치하는 문자를 찾고, 문자열이 일치하지않는다면, 사전에 추가하며, 일치하는 문자열의 Index(색인 번호)를 출력하는 문제다. 풀이 우선 이 문제에서 msg의 길이는 최대 1,000이다. 완전탐색으로 구현할 경우, 최악의 경우는 (아마)다음과 같을것 이다. msg : ..

티스토리툴바