본문 바로가기
반응형

BOJ

[BOJ 19585] 전설 [문제] www.acmicpc.net/problem/19585 19585번: 전설 Sogang ICPC Team에는 색상 이름과 닉네임의 순서로 이여서 팀명을 지으면 ICPC 리저널에서 수상할 수 있다는 전설이 있다. 색상 이름들과 닉네임들이 주어질 때, Q개의 팀에 대해 다음 리저널에서 수 www.acmicpc.net [난이도] - Platinum 3 (solved.ac 20.12.10 기준) [필요 개념] - 트라이 (Trie) / (해싱) [풀이] 처음에는 색상과 닉네임을 모두 하나의 트라이에 넣고, 팀명을 탐색하면서 색상과 일치하는 모든 위치를 찾아 해당 위치 이후의 문자열들을 잘라 다시 트라이에 넣어서 닉네임과 일치하는지를 체크하였는데 83%에서 TLE가 발생했다. 만약 팀명이 2000자이고, ..
[BOJ 3080] 아름다운 이름 [문제] www.acmicpc.net/problem/3080 3080번: 아름다운 이름 상근 선생님은 학생들에게 번호를 붙여주려고 한다. 상근이는 미술 선생님이기 때문에, 이름의 순서도 아름다워야 한다고 생각한다. 따라서, 다음과 같은 규칙을 지켜서 번호를 정하려고 한다. www.acmicpc.net [난이도] - Platinum 2 (solved.ac 20.12.10 기준) [필요 개념] - 트라이 (Trie) - 재귀 - 순열 [풀이] 문제의 조건을 해석해보면, 특정 index에서 묶이는 문자열들이 있다. 예제 2를 통해서 이해해보자. 같은 알파벳 순서로 시작하는 두 이름 사이에는 모두 그 순서로 시작하는 단어가 있어야 한다. 이 말은, 같은 알파벳 순서로 시작하는 이름들은 모두 이웃해야 한다는 의미..
[BOJ 1533] 길의 개수 [문제] www.acmicpc.net/problem/1533 1533번: 길의 개수 첫째 줄에 교차점의 개수 N이 주어진다. N은 10보다 작거나 같고, 시작점의 위치 S와 끝점의 위치 E, 그리고 정문이가 늦는 시간 T도 주어진다. S와 E는 N보다 작거나 같은 자연수이다. T는 1,000,000,000 www.acmicpc.net [난이도] - Platinum 4 (solved.ac 20.11.28 기준) [필요 개념] - 그래프 - 분할 정복을 이용한 거듭제곱 [풀이] 가중치가 없는 그래프인 경우, 0 또는 1로 이루어진 그래프의 인접 행렬이 주어질 때 i에서 N번 이동해서 j로 가는 경우의 수는 인접행렬의 N제곱의 (i, j) 값이다. 이를 이용하기 위해서 가중치가 주어지는 이 문제의 그래프를 조..
[BOJ 1073] 도미노 [문제] www.acmicpc.net/problem/1073 1073번: 도미노 은진이는 도미노 게임을 좋아한다. 도미노는 직사각형 모양이고, 두 개의 정사각형으로 나누어져 있다. 그리고, 각 정사각형에는 0보다 크거나 같고, 9보다 작거나 같은 정수가 하나 쓰여 있다. www.acmicpc.net [난이도] - Platinum 4 (solved.ac 20.11.06 기준) [필요 개념] - 오일러 회로 (Eulerian Circuit) [풀이] (이 블로그를 참고했습니다. wootool.tistory.com/46) 이 문제는 코드나 풀이가 상당히 간단하지만, 생각해내기가 쉽지 않은 문제이다. 우선 오일러 회로 개념에 대한 이해가 필요하다. 짧게 설명하면, 무향 그래프에서 그래프의 시작점으로부터 출발해서..
[BOJ 5821] 쌀 창고 [문제] www.acmicpc.net/problem/5821 5821번: 쌀 창고 첫째 줄에 R, L, B가 주어진다. 둘째 줄부터 R개 줄에는 X[i]가 주어진다. (1 ≤ R ≤ 100,000, 1 ≤ L ≤ 1,000,000,000, 0 ≤ B ≤ 2,000,000,000,000,000) www.acmicpc.net [난이도] - Platinum 4 (solved.ac 20.10.29 기준) [필요 개념] - 이분 탐색 (Binary Search) - 누적 합 (Prefix Sum) [풀이] 각 논들이 일직선상에 주어져 있고, 해당 논을 수확하기 위해서는 쌀 창고와의 거리만큼 비용이 필요하다. 지불할 수 있는 비용 한도가 정해져 있고, 한도 내에서 쌀 창고의 위치를 잘 정해줘서 수확할 수 있는 최대..
[BOJ 2672] 여러 직사각형의 전체 면적 구하기 [문제] www.acmicpc.net/problem/2672 2672번: 여러 직사각형의 전체 면적 구하기 첫째 줄에 직사각형의 개수 N(1 ≤ N ≤ 30)이 주어지고 그 다음 N줄에는 각각의 직사각형에 대한 자료가 주어진다. 이 자료는 4개의 숫자로 표시되는데 첫째, 둘째 숫자는 직사각형의 왼쪽 아래 모 www.acmicpc.net [필요 개념] - 스위핑 (Sweeping) [난이도] - Gold 2 (solved.ac 20.10.29 기준) [풀이] N의 크기가 작아서 여러 풀이 방법이 가능하지만, 대체로 이런 유형은 '스위핑'으로 풀리는 경우가 많다. 우선, 주어지는 입력이 조금 특이한데 알고 보면 크게 다르지 않다. 각 사각형의 왼쪽 아래 꼭짓점의 좌표와 사각형의 폭, 높이가 소수로 주어진다...
[분할 정복] L-트로미노(L-Tromino) 타일링 1. 트로미노란? 트로미노(Tromino)란, n=3인 폴리오미노(polyomino)로, 크기가 같은 정사각형 3개를 변끼리 붙여 만든 다각형이다. 따라서 다음과 같이 두 개의 트로미노가 존재할 수 있다. 2. $2^n$ x $2^n$ L-트로미노 타일링 이제, 이 트로미노중에서 일자형이 아닌 L 모양의 트로미노를 한 변의 길이가 $2^n$인 정사각형에 배치하는 것이 목표이다. 결론부터 말하자면, L-트로미노는 1x1 한 칸을 제외하고, 한 변의 길이가 $2^n$인 정사각형을 항상 채울 수 있다. 증명은 다음과 같이 수학적 귀납법으로 가능하다. [정리] $2^n$ X $2^n$ 크기의 정사각형에 1x1 한 칸을 제외하고 항상 L-트로미노로 모두 채울 수 있다. [증명] 1. n = 1일 때 n = 1인 ..
[BOJ 2336] 굉장한 학생 [문제] : https://www.acmicpc.net/problem/2336 2336번: 굉장한 학생 문제 N명의 학생이 참여하여 세 번의 시험을 치렀다. N명의 학생들은 세 번의 시험에 모두 응시하였다. 조교는 각각의 시험에서 같은 등수의 학생이 한 명도 없도록 성적을 매겼다. A라는 학생이 www.acmicpc.net [난이도] - Platinum 2 (2020.08.05 solved.ac 기준) [개념] - 세그먼트 트리 (Segment Tree) [풀이] 우선 https://jason9319.tistory.com/57 블로그의 설명을 참고하여 풀이를 하였다. 문제를 요약하자면, 각 학생이 세 번의 시험에 참여하였고, 학생 A보다 세 과목이 모두 더 높은 등수인 사람이 없다면 A를 '굉장하다'라고..

티스토리툴바