공부방

삼각형을 이어붙여 다음 삼각형의 변의 길이를 구하는 문제이다. 규칙을 찾아보면 처음 P(1), P(2), P(3)은 1로 고정이고 그 다음부터 P(n-2)+P(n-3) = P(n) 이 되는것을 알 수 있다. 재귀함수를 사용하여 다음과 같이 나타낼 수 있다. 다만 이렇게 만들게 된다면 큰 수를 표현할 때 시간이 엄청 오래걸리게 된다. 예를 들어 80번째의 수를 구하기 위해서는 78, 77 번째의 수를 구해야 하는데 이때 각 78 77번째의 수를 구하기 위해서는 또 75 76, 74 75번째의 수를 구해야 하고 ... 이런식으로 수없이 많은 계산을 반복해야 한다. 이 시간을 줄이기 위해 배열을 생성하여 배열에 각 값들을 저장해 두게 되면 반복되는 계산이 줄어들게 되므로 시간이 단축되는 효과가 있다. 이처럼 ..

V높이의 나무를 하루에 A만큼 올라가고 B만큼 미끄러지면서 얼마만에 꼭대기에 도달하는지 찾는 문제. 보기엔 얼핏 간단해 보이나 시간 제한(0.15초)가 걸린다. 간단히 작성해 보았다. a b v 는 주어진 보기와 같고 ht 는 달팽이의 현재 위치, 그리고 count는 날짜를 세는 용도이다. 날이 밝았을 때 a만큼 올라간 후 현재위치(ht)를 목표위치(v)와 비교하여 도달하면 반복문을 빠져나오고, 도달하지 못한다면 밤이되어 b만큼 미끄러지는 식으로 작성하였으나 결과는 역시 시간 초과. 따라서 변수를 더 추가한 후 간단히 구할 방법을 생각해보았다. 달팽이가 하루에 올라가는 높이를 구한 후 전체 높이에서 나눈다면 간단히 몇일이 걸리는지 알 수 있다. 다만 단순히 v / (a-b) 를 하게 된다면 100 99 ..

주어진 a와 b값의 최소공배수를 구하는 문제이다. 최소공배수는 a와 b의 공배수 중 가장 작은 수이므로 단순히 두 수중 큰 수부터 시작하여 하나씩 비교하는 방식으로 쉽게 구할 수 있다. 위와 같이 먼저 a와 b의 값을 비교하여 큰 수를 b쪽에 두고, while문을 이용하여 b값을 시작값으로 두고 1씩 증가시키면서 조건(공배수)을 만족시키는 값을 찾을 수 있다. 다만 이렇게 구하게 되면 시간이 굉장히 오래걸리기 때문에 위와 같은 코드로 제출하게 되면 시간 초과라는 오류가 발생하게 된다. 따라서 조금 다른 방식으로 구해보았다. 최소공배수는 두 수의 곱 / 최대공약수 로 구할 수 있기 때문에 먼저 최대공약수를 구한다. 최대공약수는 1부터 두 수중 작은 수까지로 한정되어 있기 때문에 비교적 짧은 시간에 값을 구..

먼저 두 수를 비교하여 큰수와 작은수를 나눈다. 나눈 이유는 for문에서 작은수 까지만 반복하면 되기 때문에 일부러 큰수와 작은수를 정하는 구문을 넣었다. for문에서는 최대공약수를 찾기 위해 1부터 두 수중 작은 수까지 반복하면서 큰수를 i로 나누었을때, 그리고 작은 수를 i로 나누었을 때 모두 나머지가 0이 되는 수(공약수)를 찾아 gcd변수에 넣는다. for문을 빠져나왔을 때 gcd의 값은 공약수 중 가장 큰 최대공약수가 된다. 두번째 while문에서는 최소공배수를 구한다. 먼저 차례로 증가할 수 j를 만든 후 lcm(최소공배수)가 0인 동안 반복하도록 한다. 위와 마찬가지로 이번에는 j를 큰 수로 나누었을때, j를 작은 수로 나누었을 때 나머지가 모두 0이 되는 j값을 찾는다. 가장 작은 j값을 ..

주어진 조건에 맞게 N개의 정수의 합을 Test 클래스로 sum()메소드를 이용해 정수의 합을 리턴하면 된다. 배열에 들어있는 수들의 합은 for문을 이용하면 쉽게 구할 수 있다. 주어진 조건대로 Test클래스에 sum이라는 함수를 만들었다. 나는 sum 변수를 생성하여 sum에 합을 담은 후 리턴했지만 답을 제출할 때에는 ans라는 변수가 주어지므로 조건에 맞게 변형시키면 되겠다. 밑의 main메소드는 올바르게 실행하는지 확인하기 위해 작성해본 코드이므로 백준알고리즘 정답을 확인할 때에는 제외하고 위의 Test 클래스만 제출하면 된다.

보기에 간단해 보이는 문제이다. sosu()메소드를 만들어서 m부터 n까지의 소수를 차례대로 구하는 코드를 작성했으나 시간 초과로 실패 이러한 시간 초과 문제를 해결하기 위해서는 에라토스테네스의 체를 이용하면 된다. '에라토스테네스의 체' 란 그리스의 수학자이자 지리학자인 에라토스테네스가 고안한 소수(素數)를 찾는 방법으로, 이 방법으로 소수를 찾으려면, 2부터 시작해 자연수를 차례로 쓴 다음, 2 이외의 2의 배수, 3 이외의 3의 배수, 5 이외의 5의 배수의 순서로 수를 지워나간다. 차례대로 지워나갔을 때 남아있는 수는 소수가 된다. 즉 배열을 생성한 후 에라토스테네스의 체를 이용하여 2의배수, 3의배수,... 를 차례대로 걸러내고 남는것을 출력하면 되겠다. n+1개의 배열을 만들고 2의 배수부터 ..

기본 문제이긴 하지만 Java를 사용할 때에는 char형을 입력받는 방법이 없다. 따라서 String형을 이용해 문자열을 입력 받은 후 charAt() 함수를 이용하여 문자열에서 문자를 분리하여 char형으로 입력하는 방식으로 입력하여야 한다. 따라서 t라는 변수에 문자열로 입력받은 후 가장 첫 문자를 char형으로 바꾸어 a라는 변수에 저장한다. 이때 결과값은 예제처럼 숫자(아스키코드값)로 출력되어야 하므로 a는 int형으로 설정한다.

첫번째 숫자와 두번째 숫자를 비교해서 각 케이스별로 결과값을 출력하는 함수 첫번째 숫자와 두번째 숫자를 입력받는다 다만 두 수가 모두 0인경우 종료.

시간이 굉장히 많이 걸렸던 문제이다. 먼저 거리가 1부터 차례대로 증가할 때마다 다음과 같이 이동하는 것이 최소값이라는것을 확인한다. 위의 규칙에 따르면 4, 9, 16처럼 제곱수 마다 횟수가 1씩 증가하는 것을 알 수 있는데 이 때 거리가 x^2일때 이동횟수가 x+(x-1)이라는 것을 알 수 있다. 다만 (x-1)^2 과 x^2 사이에 작동횟수가 한번 증가하는 구간이 있는데 이 구간은 x^2 - (x-1)^2 의 중간값이므로 몫을 구하는 / 연산자를 이용하여 계산해준다. 위의 조건에 따라 함수를 작성한 것이다. 처음 설정을 int로 해 두는 바람에 시간 초과라는 에러 표시가 발생했다. 만약 변수를 int로 설정할 경우 거리 dis 보다 큰 제곱수 i 를 찾을 때 오버플로우가 발생해버리게 된다. 따라서 ..