본문 바로가기

ICPC

(8)
[백준 / BOJ] 10891 Cactus? Not cactus? (cpp) 문제 출처 : https://www.acmicpc.net/problem/10891 10891번: Cactus? Not cactus? 첫 번째 줄에 그래프의 정점의 개수와 간선의 개수를 나타내는 두 정수 N,M (1 ≤ N,M ≤ 100,000) 이 공백으로 구분되어 주어진다. 다음 M개의 줄에는 간선이 연결하고 있는 두 정점을 나타내는 두 정 www.acmicpc.net 양방향 그래프에서 각 정점에서 시작해 자기 자신으로 돌아오는 사이클이 2개 이상이라면 Cactus가 아니며, 하나 이하라면 Cactus이다. 이 때, 주어진 그래프가 Cactus인지 Not cactus인지 출력하는 문제다. 풀이 처음에는 단절점을 찾고, 단절점에 대해 자식 트리가 2개 이상이라면 Not cactus를 출력하게 해줬는데, ..
[백준 / 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] 1195 킥다운 문제 출처 : https://www.acmicpc.net/problem/1195 1195번: 킥다운 첫 줄에는 첫 번째 기어 파트를 나타내는 1과 2로 구성된 문자열이 주어진다. 두 번째 줄에는 마찬가지로 두 번째 기어 파트를 나타내는 1, 2로 구성된 문자열이 주어진다. 여기서 1은 홈을, 2는 www.acmicpc.net 두개의 기어파트가 주어진다. 각 기어파트는 1과 2로 이루어져있는데, 1은 '홈(들어가있는 부분)' 2는 '이(나와있는 부분)'를 나타낸다 이 때, 두개의 기어파트를 적절히 조합하여 조합된 기어파트의 길이의 최솟값을 구하는 문제다. 풀이 기어의 길이가 최대 100이므로 완전탐색으로 풀리는 문제다. 문제에서 주어진 그대로 구현하면 되는데, 몇가지 주의할 점 이 있다. - 기어가 맞물린..
[백준 / BOJ] 20925 메이플스토리 문제 출처 : https://www.acmicpc.net/problem/20925 20925번: 메이플스토리 첫째 줄 사냥터 수 $N$ ($1 \le N \le 200$)과 방학 기간을 분 단위로 나타낸 $T$ ($1 \le T \le 1\,000$)가 주어진다. 다음 $N$개의 줄에는 $i$번째 사냥터의 특징인 입장에 필요한 최소 경험치 $c_i$와 $1$분마 www.acmicpc.net 상원이는 메이플스토리를 할 것이다. 상원이의 캐릭터가 갈수있는 사냥터의 수 N 상원이가 사냥할 시간 T 가 주어지고, 이후, N개의 줄에 각 던전에 입장하는데 필요한 최소경험치와 시간당 주는 경험치가 주어진다. 상원이가 T시간동안 사냥했을때 얻을 수 있는 최대 경험치를 구하는 문제다. 풀이 dp로 푼 문제였다. 처음에..
[백준 / BOJ] 20921 그렇고 그런 사이 문제 출처 : https://www.acmicpc.net/problem/20921 20921번: 그렇고 그런 사이 정수 $N$, $K$가 주어진다. ($2 \leq N \leq 4\,242$, $0 \leq K \leq \frac{N(N-1)}{2}$) www.acmicpc.net 환주는 두명을 그렇고 그런 사이로 만드는데 전문가이다. 그렇고 그런 사이가 될려면, 다음 조건을 만족해야한다. (P(i)가 갖고있는 숫자가 P(i+a)보다 커야함) (단, a>0) 환주의 친구의수 N, 그렇고 그런 사이로 만들어야하는 쌍의수 K가 주어졌을때, 그렇고 그런 사이를 만드는 경우를 출력하는 문제다. 풀이 재밌는..? 문제였다. 문제를 처음 봤을때는 감이 잘 안잡혔는데,(dp라고 예상했었음) 문제의 예제를 직접 해보니..
[백준 / BOJ] 9466 텀 프로젝트 문제 출처 : www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 문제 해결 강의를 신청한 학생들은 텀 프로젝트를 수행해야한다. 각 학생들마다 팀을 하고싶은 학생이 다르고, 한 학생이 한명의 학생만 선택할수있다. 학생들의 팀원선택이 사이클을 이루면 해당 학생들은 팀을 이뤘다고할때, 팀을 이루지못한 학생들의 수를 구하는 문제다. 풀이 학생들의 사이클을 찾으면 되는 문제인데, 시간초과를 조심해야한다. 풀이의 핵심은 한 학생을 기준으로 그룹을 찾을때마다, 해당 그룹안에 포..
[백준 / BOJ] 18679 Banana 문제 출처 : www.acmicpc.net/problem/18679 18679번: Banana The first line of input will contain a single integer N, the number of words in the dictionary (1 ≤ N ≤ 100). The following N lines will each contain a sentence of the format x = y where x is an English word and y is a Minionese word. The next line wil www.acmicpc.net 입력 받은 문자를 미니언 언어로 바꿔서 출력하면된다. 예를들어, I love banana -> mo amo banana 입력에서 각 문자..
[백준 / BOJ] 2233 사과나무 문제 출처 : www.acmicpc.net/problem/2233 2233번: 사과나무 문제 사과나무는 나무(tree)의 일종으로, 각각의 정점에 정확히 한 개의 사과가 있고, 모든 내부 정점(자식이 있는 정점)이 최소 두 개의 자식을 갖는 나무이다. 예를 들면 아래의 그림은 사과나무 www.acmicpc.net 정점의 개수와 벌레가 만드는 이진수를 입력받고, 정상적인나무를 최소화한상태로 썩은나무를 모두 없애는 정점을 구하는 문제다. 풀이 그래프 구조를 만들필요없이 해당노드의 등장 순서만 알고있다면 풀리는 문제다. 입력을 보면, 벌레가 만드는 이진수가 깊이우선탐색의 순서와동일한것을 알수있다. (해당 노드에서 끝까지 간후 더이상 갈수없을경우, 부모로 올라감) -이진수에 따라 자식과 부모관계를 만들어주기위해..