[백준][BOJ 2422] - Ice Cream
2023. 10. 4. 17:04
Algorithm/BruteForce
문제 https://www.acmicpc.net/problem/2422 2422번: 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 첫째 줄에 정수 N과 M이 주어진다. N은 아이스크림 종류의 수이고, M은 섞어먹으면 안 되는 조합의 개수이다. 아래 M개의 줄에는 섞어먹으면 안 되는 조합의 번호가 주어진다. 같은 조합은 두 번 www.acmicpc.net 문제 접근 1부터 N까지의 수들 중 3개를 뽑는 경우의 수를 구하는 문제 단 제약 조건이 달려 있는데 섞어먹으면 안되는 조합이 존재한다는 것이다. 만약 1은 2와 섞일 수 없다 라고 한다면 (1, 2, X) 로 되어 있는 모든 조합은 카운팅되지 않는다는 것이다. 즉 3개를 뽑은 뒤 각각의 수가 섞일 수 없는 수에 포함되어 있는지를 한 번 더 체크해야 ..
[백준][BOJ 1251] - 단어 나누기
2023. 10. 4. 12:59
Algorithm/BruteForce
문제 https://www.acmicpc.net/problem/1251 1251번: 단어 나누기 알파벳 소문자로 이루어진 단어를 가지고 아래와 같은 과정을 해 보려고 한다. 먼저 단어에서 임의의 두 부분을 골라서 단어를 쪼갠다. 즉, 주어진 단어를 세 개의 더 작은 단어로 나누는 것이다 www.acmicpc.net 문제 접근 입력으로 주어진 단어에 대해 문자열을 나누어 뒤집고, 이를 다시 조합하는 것이 가장 핵심적인 로직이다. 이때 만들 수 있는 모든 단어를 만들어야 하므로 어떻게 문자열을 나눌 것인지를 생각해야 한다. 모든 경우의 수를 따져보아야 하므로 문제에서 제시된 조건인 각각의 문자열은 적어도 길이 1 이상이어야 한다를 만족하도록 문자열을 나누어 주면 된다. 2중 for문으로 만들어낼 수 있다. ..
[백준][BOJ 1448] - 삼각형 만들기
2023. 10. 4. 12:15
Algorithm/Greedy
문제 https://www.acmicpc.net/problem/1448 1448번: 삼각형 만들기 첫째 줄에 빨대의 개수 N이 주어진다. N은 3보다 크거나 같고, 1,000,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 빨대의 길이가 한 줄에 하나씩 주어진다. 빨대의 길이는 1,000,000보다 www.acmicpc.net 문제 접근 삼각형 세 변의 길이의 합의 최댓값을 구해야 한다. 이때 삼각형의 조건을 만족할 수 있어야 한다. 즉 가장 긴 변의 길이가 나머지 두 변의 길이의 합보다 작아야 한다는 조건을 만족해야 한다. 가장 나이브한 풀이는 완전 탐색을 사용하여 N개 빨대 중 3개를 선택하여 삼각형의 조건에 부합하는지를 검사하고, 통과한다면 그 합을 구해 최대 값을 갱신하는 방식이다. ..
[백준][BOJ 9017] - 크로스 컨트리
2023. 10. 3. 20:12
Algorithm/DataStructure
문제 https://www.acmicpc.net/problem/9017 9017번: 크로스 컨트리 입력 데이터는 표준입력을 사용한다. 입력은 T 개의 테스트 케이스로 주어진다. 입력 파일의 첫 번째 줄에 테스트 케이스의 수를 나타내는 정수 T 가 주어진다. 두 번째 줄부터는 두 줄에 하나의 www.acmicpc.net 문제 접근 점수를 구할 때 6인보다 적은 팀은 점수 계산에 상정되지 않는다는 것을 유의해야 한다. 이는 즉 입력에서부터 각 팀원당 몇 명이 소속 되어 있는지를 확인해야 한다. 또한 상위 4인 까지의 점수의 합으로 먼저 판단한 뒤 동점이 나올 시 5번째로 들어온 사람의 점수를 사용하여 최종적으로 판별하는 것을 유의해야 한다. Map을 사용하면 매우 쉽게 구현이 가능한 문제였다. 정렬을 통해 ..
[백준][BOJ 20920] - 영단어 암기는 괴로워
2023. 10. 3. 15:21
Algorithm/DataStructure
문제 https://www.acmicpc.net/problem/20920 20920번: 영단어 암기는 괴로워 첫째 줄에는 영어 지문에 나오는 단어의 개수 N과 외울 단어의 길이 기준이 되는 M이 공백으로 구분되어 주어진다. (1≤N≤100000, 1≤M≤10) 둘째 줄부터 N+1번째 줄까지 외울 단 www.acmicpc.net 문제 접근 자주 나오는 단어일수록 앞에 배치된다. 단어의 길이가 길수록 앞에 배치한다. 알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치한다 이때 길이 M미만의 단어는 무시한다. 먼저 빈도수를 잘 계산하기 위해 key-value로 O(1) 시간에 접근이 가능한 map을 사용하였다. 이후 위의 우선순위에 맞도록 정렬을..
[백준][BOJ 10431] - 줄세우기
2023. 10. 3. 14:10
Algorithm/Simulation, Implement
문제 https://www.acmicpc.net/problem/10431 10431번: 줄세우기 초등학교 선생님 강산이는 아이들을 데리고 단체로 어떤 일을 할 때 불편함이 없도록 새로 반에 배정받은 아이들에게 키 순서대로 번호를 부여한다. 번호를 부여할 땐 키가 가장 작은 아이가 1 www.acmicpc.net 문제 접근 삽입 정렬의 구현을 조금 변형하여 구현하는 문제였다. 현재 데이터 보다 큰 데이터가 앞에 있는 그 즉시 큰 데이터를 포함하여 그 뒤에 있는 모든 데이터를 한 칸씩 뒤로 옮기는 부분이 가장 핵심적인 기능이었다. 모든 데이터를 한 칸 뒤로 옮기게 되면 현재 데이터보다 큰 데이터가 있던 자리에 현재 데이터를 삽입(insert)하는 방식으로 구현하면 끝나는 문제였다. 정답 코드 import j..
[백준][BOJ 2502] - 떡 먹는 호랑이
2023. 10. 2. 19:07
Algorithm/DP
문제 https://www.acmicpc.net/problem/2502 2502번: 떡 먹는 호랑이 첫줄에 첫 날에 준 떡의 개수 A를 출력하고 그 다음 둘째 줄에는 둘째 날에 준 떡의 개수 B를 출력한다. 이 문제에서 주어진 D, K에 대해서는 항상 정수 A, B (1≤ A ≤ B)가 존재한다. www.acmicpc.net 문제 접근 점화식이 이미 문제에서 주어져 있다. 점화식은 다음과 같이 주어진다. Ak=Ak−1+Ak−2 문제에서 요구하는 답은 특정 시점과 떡의 개수가 주어질 때 초기값을 구하라는 것이다. 이때 문제 조건에서 항상 A1≤A2를 만족한다는 것을 유의하라 A1은 특정 시점에 주어진 떡의 개수를 K라고 할 때 K/2까지 될 수 있..
[백준][BOJ 1969] - DNA
2023. 10. 2. 14:29
Algorithm/BruteForce
문제 https://www.acmicpc.net/problem/1969 1969번: DNA DNA란 어떤 유전물질을 구성하는 분자이다. 이 DNA는 서로 다른 4가지의 뉴클레오티드로 이루어져 있다(Adenine, Thymine, Guanine, Cytosine). 우리는 어떤 DNA의 물질을 표현할 때, 이 DNA를 이루는 뉴클레오 www.acmicpc.net 문제 접근 주어진 DNA입력들에 대해 Hamming Distance가 최소가 되는 DNA를 우리가 만들어야 한다. Hamming Distance의 경우 우리가 만든 DNA를 s라고 할 때 이 s의 각 부분과 주어진 DNA들의 각 부분을 비교해 다른 글자의 개수로 정의된다. 따라서 Hamming Distance를 최소화 시키기 위해서는 주어진..
[백준][BOJ 4134] - 다음 소수
2023. 10. 2. 13:06
Algorithm/BruteForce
문제 https://www.acmicpc.net/problem/4134 4134번: 다음 소수 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. www.acmicpc.net 문제 접근 N보다 크거나 같은 소수 중 가장 작은 소수를 구하는 문제 N이 최대 4억까지 주어질 수 있고, 어디까지 진행되는지도 알 수 없기 때문에 수 자체는 넉넉하게 long으로 잡았다. 생각해보면 그냥 int도 21억까지 지원하기 때문에 int로 해도 무방할 것 같기도 하다 이후에는 N을 1씩 증가시키며 소수인지를 판별했다. 소수를 판별하는 방식은 여러가지가 있지만 나는 루트를 적용하여 범위를 줄이는 방식을 사용하였다. 정답 코드 import java.io.Buf..
[백준][BOJ 2210] - 숫자판 점프
2023. 10. 2. 12:33
Algorithm/BruteForce
문제 https://www.acmicpc.net/problem/2210 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net 문제 접근 숫자판의 임의의 위치에서 인접한 4방향으로 5번 이동하면서 숫자판에 적힌 숫자를 붙이는 것이 핵심적인 기능이다. 이동 시에 이미 방문했던 칸을 다시 방문해도 상관없다는 조건이 붙어 있다. 숫자가 0인 경우에도 0으로 시작하는 수를 만들 수 있다. 위의 규칙을 만족시키면서 숫자판에서 이동할 때 나올 수 있는 모든 숫자의 개수를 구하는 것이 ..