pinevienna blog

달팽이가 낮에는 A미터 올라가고 밤에는 B미터 미끄러진다.. 높이가 V미터인 막대의 정상에 올라가기 위해 며칠이 걸리는지 구하는 문제 시간제한이 있는 문제다... 잘못풀면 시간초과가 뜬다 (경험담) 주의할 점은 정상에 올라가면 미끄러지지 않는다는 점이다 그러니까 밤에 미끄러진 후 V-A미터에 도달하면 그 다음날에 바로 정상에 올라갈 수 있다!! 도달하지 않는다면..? 2미터 모자라면..? 3미터.. 4미터 막 모자라면..?은 생각할 필요가 없다 어쨌든 (V-A)를 (A-B)로 나누었을 때 1미터라도 남는다면 나눈 값에서 이틀 더 걸리는 것이다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 #include using namespace std; int main(void) { io..

이거 풀 때 지그재그를 잘못 이해해서 개고생 했던 기억이 난다.. 암튼 위와 같은 지그재그 순서로 배열을 읽을 때, n번째 분수는 무엇인지 출력하면 된다 이렇게 대각선으로 1, 2, 3 ··· 번호를 매겨보자 (1씩 증가하는 등비수열) 이 번호가 홀수일 때는 ↙ 이 방향으로 숫자를 세고, 짝수일 때는 ↗ 이렇게 센다 이걸 캐치하면 쉬워진다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 #include using namespace std; int main() { int n, cnt = 0; cin >> n; while (n > 0) { cnt++; n -= cnt; } if (cnt % 2 == 0) cout

육각형으로 된 벌집! 중앙의 1부터 시작해서 이웃하는 방에 +1씩 번호가 매겨진다 n번째 방에 최소한의 방만 거쳐서 간다면 몇 개의 방을 거쳐야 하는지 구하는 문제 1번 방은 1 2~7번 방은 2 8~19번 방은 3 20~37번 방은 4 · · · 동그랗게 이어진 방들 중 마지막 방만(1, 7, 19, 37 ··· ) 보면 1 + 6 + (6*2) + (6*3) + ··· 이렇게 증가하는걸 볼 수 있다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 #include using namespace std; int main(void) { int n, i = 1, sum = 1; cin >> n; if (n == 1) cout

고정비용과 가변비용, 제품의 가격을 입력받아 손익분기점을 구하는 문제 반복문으로 수입이 비용을 넘기는 순간을 구해야할 것 같이 생겼지만 아니다 제품 가격에서 가변비용을 뺀 값으로 고정비용을 나누고 +1 해주면 된다 가변비용은 제품을 만들 때 마다 드는 비용이므로 그냥 상쇄시키는 것이라고 보면 된다! 1 2 3 4 5 6 7 8 9 10 11 12 13 14 #include using namespace std; int main(void) { int a, b, c; int cnt = 1; cin >> a >> b >> c; if (b >= c) cout

한국어로는 탐욕 알고리즘이라고 한다 탐욕적으로.. 최적값을 가진 데이터들로 최적해를 찾기 때문이다 예제를 보면 이해가 쉽다 1원 ~ 50000원 동전을 적절히 더해서 4200을 만들면 되는데, 최소한의 동전만 써야 한다 1원짜리 4200개, 5원짜리 840개, 10원짜리 420개 ··· 당연히 액수가 큰 동전을 많이 쓸수록 동전의 개수가 적어진다 그럼 탐욕스럽게 역순으로 가보자 50000 X, 10000 X, 5000 X, 1000원짜리 4개, 500 X, 100원짜리 2개 → 6개 라는 결과를 구할 수 있다 이런 걸 그리디 알고리즘이라고.. 한다는데 사실 이게 그리디 알고리즘인지 뭔지도 모르고 풀 확률이 크다 그게 그리디 알고리즘의 특징이라고 한다 조금 더 어려운 문제! 하나의 회의실에 최대 몇 개의 ..