Algorithm/OnlineJudge
p384 ( Slurpys )
Slump 조건 1. D or E로 시작 2. 첫 글자 이후엔 F가 1개 이상은 반드시 옴. 3. F이후에 Slump또는 G가 와야함 Slimp 조건 1. A로 시작. 2. 총 두글자라면 반드시 AH여야함. 3. 길이가 2 이상이면 두 가지 경우가 있음. -> AB(Slimp)C -> A(Slump)C Slurpy 조건 Slimp에 이어서 Slump가 나오는 문자열 조건에따라 주어진 문자열이 Slurpy가 맞는지 확인하는 문제입니다. isSlump()와 isSlimp() 함수를 재귀적으로 작동하게 만들어서 풀었습니다. 먼저 처음으로 주어진 문자열에서 D 또는 E의 바로 이전에 C가 있는 경우를 찾아서 전체 문자열을 Slimp와 Slump로 나눴습니다. Slump의 경우 F가 등장한 경우 계속해서 진행하며..
p10010 ( Where's Waldorf )
문제 문자들이 적혀있는 표( 배열, 격자 ) 에서 왼쪽 위에서부터 오른쪽 밑으로 탐색하여 찾고자 하는 문자열을 8방향으로 탐색, 탐색에 성공하면 현재 위치를 출력하는 문제이다. 추가조건으로 문자의 대소문자를 구분하지 않는다. 위의 예제에 대하여 나타내면 다음과 같다. 입력되는 격자의 최대 크기가 50 x 50이고, 찾는 문자열의 길이는 최대 20이다. 격자의 각 위치마다 8방향을 탐색하고, 최대 길이가 20이므로 단순하게 50 x 50 x 8 x 20으로 계산을 해보더라도 40만이다. 그냥 좌측 위를 ( 0, 0 )으로 두고 오른쪽 아래로 나아가며 8방향 탐색을 하면 된다고 판단했다. 소스코드. 더보기 #include #include using namespace std; #pragma warning(di..
p10150 ( Doublets )
문제 동일한 길이의 두 문자열의 차이가 한 글자만 있는 경우 Doublet이라 한다. 단어사전에 해당하는 문자열이 한줄에 하나씩 나열되며, 두 문자열이 공백을 기준으로 나뉘어져 입력이 들어오게되면 출력을 해야함을 의미한다. 출력은 입력으로 들어온 두 문자열 중에서 앞의 것을 시작 단어, 뒤의 것을 끝 단어로 둔다. 시작단어부터 현재 단어와 Doublet관계에 있는 단어를 타고 다음 단어로 이동이 가능하다. 끝 단어에 도착하게 되면 지금껏 타고온 단어들을 순서대로 출력해야한다. (단, 제일 빠르게 끝 단어에 도착한 순서를 출력해야한다. ) 문자열의 최대길이는 16이며, 입력되는 단어의 최대개수는 25143개 이다. booster rooster boosted roaster coasted roasted coa..
p679 ( Dropping Balls )
FBT, 완전 이진 트리에 대하여 푸는 문제. FBT의 모든 노드는 초기값이 false로 세팅되어있고, 공은 루트노드부터 떨어진다. 공이 거쳐간 노드는 값이 반전( false라면 true로, true라면 false로 ) 되며, false였다면 왼쪽으로 공이 떨어지고 true면 오른쪽으로 떨어진다. 트리의 높이와 공을 떨어뜨린 횟수가 주어졌을 때, 마지막에 떨어진 공이 위치하는 노드의 값을 출력하는 문제. 공은 리프노드까지 떨어진다. 풀이 더보기 위와 같은 트리에서 공을 떨어트릴 수 있는 기회는 총 8번이다. ( 리프노드까지 공이 떨어지므로 ) 이를 숫자로 표현하여 다시 나타내보면 다음과 같다. 잘 보면 루트노드를 기준으로 왼쪽 서브트리는 모두 홀수의 순서값을 가지고, 오른쪽 서브트리는 짝수의 순서값을 가..
p10137 ( The Trip )
여행경비로 지출된 총 금액을 모든 인원이 최대한 균등하게 돈을 지출하도록 만드는 문제 돈을 많이 낸 사람들과 작게 낸 사람들 중 평균값과의 차이가 더 큰 만큼 돈을 이동해야한다. 예를 들어 13.01 13 3.01 3 이렇게 돈을 냈다고 가정했을 때, 총 지출한 돈의 양은 32.02 달러이다. 이를 4로 나누게 되면 8..005달러가 되지만, 0.5센트는 없으므로 8달러와 8.01달러로 평균값을 둔다. 8달러와 8.01달러 중 작은 금액에 해당하는 8달러보다 작게낸 사람은 3.01달러와 3달러가 되고, 8.01달러보다 많이 낸 사람은 13.01달러와 13달러가 된다. 적게낸 사람들 각각 평균값과의 차이는 4.99달러, 5달러이고 많이낸 사람들 각각 평균값과의 차이는 5달러, 4.99달러이다. 적게낸 사람..
p100 ( 3n + 1)
두 수 i, j 를 입력받은 다음, 그 사이 값에 대하여 규칙에 따라 연산을 했을 때, 제일 연산을 많이 수행했을 때의 횟수를 출력하는 문제. 규칙 홀수이면 *3을 하고 1을 더한다. 짝수이면 /2를 한다 더보기 #include #include #pragma warning(disable:4996); using namespace std; int solve(int num) { int cnt = 1; while (num > 1) { cnt++; if (num % 2 == 0) { num /= 2; } else { num = num * 3 + 1; } } return cnt; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); in..