2018/05

알고리즘/CodeForces

Codeforces Round #102 (Div. 1)

A. Help Farmer$\!$ $A*B*C$의 값이 주어졌을 때, $(A + 1) * (B + 2) * (C + 2) - A * B * C$의 값의 최대, 최솟값을 구하는 문제이다. $A*B*C$의 값은 상수이므로 $(A + 1) * (B + 2) * (C + 2)$를 결정해주면 되는데, $A*B*C$의 값 $n$의 약수를 모두 돌아보며 $A$, $B$의 값을 결정해주면 된다. ($A$, $B$가 결정되면 $C$는 알아서 결정되므로 고려할 필요가 없다.)2중 for문 으로 해결되는데, 약수를 결정하고나면 그 반대 쌍도 $A$나 $B$값으로 고려하여 체크해봐야한다.(예제를 돌려보면 무슨 뜻인지 이해가 갈 것이다.) 문제는 이게 시간내에 돌아가느냐인데.. 약수결정에 O($sqrt(n)$)이 걸리고, 또 ..

알고리즘/잡설

suffix array + lcp

1. suffix array설명은 갓-crocus 블로그가, lcp설명은 plzrun 블로그가 제일 정리가 잘 되어있다. 2. suffix array의 존재이유는 lcp를 위해 있다고 해도 과언이 아니다. 3. O($nlogn$)만에 구하는 알고리즘도 있다. O($nlog^2n$) 알고리즘보고 오 기수정렬이랑 비슷하다 생각했는데 역시 radix sort를 이용한단다. 자료구조수업때 한번 본 이후로 처음 보며 처음 써본다. 제대로 이해하기 위해서는 radix sort를 다시 봐야겠다. 설명은 plzrun 블로그. 4. lcp가 이용되는 대표적인 문제는 BOJ_가장 긴 문자열 이다. 한 문자열에서 두 번 이상 나오는 문자열을 포함하는 suffix는 suffix array에서 항상 인접하고, lcp의 정의에 ..

알고리즘/CodeForces

Codeforces Round #476 (Div. 2)

A. Paper Airplanes$\!$ $k$명의 사람이 각각 $n$개의 종이비행기를 접으려 하는데 종이 1장당 종이비행기 $s$개를 만들 수 있다. 한 묶음에 $p$개의 종이가 들어있는 묶음을 몇 묶음 사야 하는지 출력하는 문제이다. 단, 1장의 종이를 찢어서 두 사람에게 나누어 줄 수가 없다. 먼저 예제를 보자. $(k, n, s, p) = (5, 3, 2, 3)$이다. 장당 2개의 종이비행기를 만들 수 있고, 한 사람이 3개의 종이비행기를 접어야 하므로 한 명당 2개의 종이가 필요하다. 5명이므로 10개의 종이가 필요하게되고, 한 묶음당 3개의 종이가 들어있으므로 총 4묶음을 사야 10개의 종이를 구할 수 있다. 즉, (($n$보다 크면서 가장 작은 $s$의 배수 $*$ k) 보다 크면서 가장 작..

알고리즘/CodeForces

Codeforces Round #478 (Div. 2)

A. Aramic script$\!$ 입력으로 문자열이 들어오는데, 각 문자열이 가지는 문자의 집합의 개수를 세는 문제이다.예를 들어 a aa aaa의 각 문자 집합은 a로 동일하므로 1을 출력해야하며, a aa aaa ab abab abbbb 는 {a}, {a, b}로 2개이므로 2를 출력해야한다. 간단히 들어온 문자열을 정렬한 뒤, unique 함수로 문자를 중복없게 뽑아낸 뒤, set에 넣어주면 된다. 한 번 틀렸는데, unique함수가 sorted 상태의 stl만 받는 다는 점.. B. Mancala 14칸 짜리 판에 구슬이 들어있는데 (0개 이상), 1개 이상의 구슬이 들어 있을 경우, 그 칸의 구슬을 모두 뽑아서 오른쪽으로 1칸씩 이동하면서 그 구슬을 1개씩 넣을 수 있다. 모두 넣고난 뒤, ..

피곤한투티
'2018/05 글 목록 (2 Page)