0과 1의 쉼터

문제계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.계단 오르는 데는 다음과 같은 규칙이 있다.계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.마지막 도착 계단은 반드시 밟아야 한다.따라서 첫 번째 계단을 밟고 이어 두..

문제The cows are playing a silly number game again. Bessie is tired of losing and wants you to help her cheat. In this game, a cow supplies a number N (1 If N is odd, then the number N is multiplied by 3 and incremented by 1. If N is even, the number N is divided by 2. Each time the number is multiplied or divided, the score increases by one point. The game ends -- and the score is finalized -- wh..

문제정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.1+1+1+11+1+21+2+12+1+12+21+33+1정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.출력각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.풀이T번 동안 1, 2, 3으로 정수 n을 만들기 위한 모든 경우의 수를 구하는 문제다.dp[i] : i를 만들 수 있는 경우의 수n을 구성하기 위해 문제에서 주어진 연산은 1, 2, 3을 합해서 만..

문제Typically, droughts are classified into “abnormally dry”, “moderate drought”, “severe drought”, “extreme drought”, and “exceptional drought”. The current drought is so “exceptional” in most of California that there have been discussions of adding one or more steps to the scale. But really, that will only delay the problem. Any system of discrete labels is not completely scalable. As computer s..

문제 https://www.acmicpc.net/problem/1463풀이N을 1로 만들기 위한 연산을 최소화하는 문제다.dp[i] : i를 만들기 위한 최소 연산 횟수기본적으로 dp[i]는 dp[i - 1]에 1을 더해 만들 수 있다, dp[i] = dp[i - 1] + 1i가 만약 2 또는 3의 배수라면, 1, 2번 연산에 의해 곱셈으로 계산하는게 이득이다.단, 2보다는 3으로 곱셈하는 것이 연산 횟수가 더 최소화되므로 dp 갱신 순서에 유의하자.소스코드보기

문제상근이는 선영이와 함께 게임을 하고 있다. 먼저, 상근이는 두 양의 정수 A와 B를 고른다. (1 ≤ B ≤ A ≤ 500) 그 다음, 선영이는 상근이가 고른 수를 맞춰야 한다.상근이는 선영이에게 다음과 같은 힌트를 주었다.A의 제곱은 B의 제곱보다 N만큼 커 (1 ≤ N ≤ 1,000)위의 힌트 조건을 만족하는 A와 B 쌍의 개수를 구하는 프로그램을 작성하시오.입력첫째 줄에 N이 주어진다.출력상근이의 힌트 조건을 만족하는 (A,B) 쌍의 개수를 출력한다.풀이1 ≤  B ≤ A ≤ 500에 대해 A^2 - B^2 == N인 경우를 세어주자.만약 찾았다면, 이후의 차는 무조건 N보다 크다. 다음 B로 넘어가자. 소스코드보기출처https://www.acmicpc.net/problem/6131

문제Farmer John has scattered treats for Bessie at special places in the pasture.  Since everyone knows that smart cows make tasty milk, FJ has placed the treats at locations that require Bessie to think. He has given her two numbers, P and Q (1 Suppose FJ gives Bessie P = 24 and Q = 2. Here are all of their respective factors:P = 24 => 1, 2, 3, 4, 6, 8, 12, 24Q = 2 => 1, 2Bessie would thus check ..

풀이원래 배열의 부분합으로 이루어진 결과 배열을 입력받아 N개의 원소로 이루어진 원래 배열을 구성하는 문제다.우선 입력받은 배열을 정렬하자. 0을 제외한 가장 작은 값이 원래 배열의 요소가 되어야 하기 때문이다.가장 작은 값과 결과 배열의 요소의 결과는 여러 수가 발생할 수 있어 Counter로 빈도를 고려했다. 결과 배열을 탐색하며 현재 요소와 가장 작은 요소의 합으로 만들 수 있는 요소가 있다면 제외( counter[num + min_element] -= count )시켜주자.현재 요소는 다음 탐색 대상이 될 수 있으니 추가해주자.원래 배열( arr )의 크기가 N이 될 때까지 다음 탐색 배열의 0이 아닌 가장 작은 값을 요소로 가지면 원래 배열을 구할 수 있다.소스코드보기출처 엘리스 코드 챌린지[엘..

풀이STATION 테이블에서 CITY의 첫 글자가 'a', 'e', 'i', 'o', 'u'로 끝나는 행을 중복 없이 출력하는 문제다.이전 문제와 비슷하다. [HackerRank] Weather Observation Station 6 [MySQL]풀이STATION 테이블에서 CITY의 첫 글자가 'a', 'e', 'i', 'o', 'u'로 시작하는 행을 중복 없이 출력하는 문제다.조건이 여러개이므로 정규 표현식을 사용해 식을 간단히해주자.소스코드보기출처 Weather Okyr-db.tistory.com 정규 표현식만 수정해주면 된다.CITY의 끝이 모음으로 끝나는지 확인하자소스코드보기출처 Weather Observation Station 7 | HackerRankQuery the list of CITY ..

풀이루트가 1번인 트리에서 하나의 말을 "두 사람이 최적으로" 번갈아가며 점수를 얻고 말을 이동하는 문제다.문제에서 주어진 두 사람이 최적으로 라는 지문의 의미는 결국 시작 정점을 기준으로 자신의 점수를 가장 높이는 방향으로 게임을 끝내는 것을 의미한다. 우선 간선을 입력받아 양방향 그래프를 생성하자.이제 dfs로 리프노드까지 탐색하며 역순으로 부모노드에 대한 점수를 계산하고자 한다.양방향 그래프이므로 자식 노드로만 탐색을 해주자.리프노드 까지 탐색을 완료했다면 가장 적은 점수차를 dp에 갱신해주자.만약 자식이 없다면(리프노드) 자신의 번호가 자신의 점수가 되므로 diff를 0으로 계산해주자. 예선 3일차에서도 유명한 문제임에 비해 예외가 적용되지 않는 오류가 있었고, 제공되는 자료와 맞지않는 문제가 주..