백준 2869 달팽이는 올라가고 싶다

2021. 2. 1. 18:52· 알고리즘/백준(BOJ)
반응형

처음 이 문제를 접근했을 때는 while문으로 낮과 밤에 올라가고 내려가는 수를 계산하기로 했었다.

예시 문제에 대한 정답은 맞았으나, 시간초과라는 결과가 떠서 다른 식으로 접근해야했는데,

문제를 보면 낮과 밤에 올라가고 내려가는 것을 수식으로 결정할 수가 있다.

 

우선 항상 모든 방식은 A - B + A - B + A - B + ... + A - B + A 패턴으로 이어지며 무조건 A가 더해지면서 끝나게 되어있다.

막대기를 다 올라간 경우 내려올 일은 없으니까.

 

따라서 걸린 일 수를 x 변수로 설정하고 수식화 하면 xA - (x-1)B >= V 가 나오고 정리하면 x >= (V - B) / (A - B) 가 된다.

 

여기서 오른쪽 식이 딱 떨어지는 경우와 아닌 경우로 나위어서 딱 떨어질 경우 그대로 x를 출력하면 되고 딱 떨어지지 않으면 int형으로 소숫점이 날아가기 때문에 +1을 해주어 출력해주면 된다.

#include <iostream>
#include <cmath>

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int A, B, V;

    cin >> A >> B >> V;

    if((V - B) % (A - B) == 0)
        cout << (V - B) / (A - B);
    else
    {
        cout << (V - B) / (A - B) + 1;
    }
    
    return 0;
}
반응형

'알고리즘 > 백준(BOJ)' 카테고리의 다른 글

백준 10757 큰 수 A + B  (0) 2021.02.03
백준 1193 분수찾기  (0) 2021.02.02
백준 2292 벌집  (0) 2021.02.01
백준 9102 괄호  (0) 2021.01.29
백준 1436 영화감독 숌  (0) 2021.01.29
'알고리즘/백준(BOJ)' 카테고리의 다른 글
  • 백준 10757 큰 수 A + B
  • 백준 1193 분수찾기
  • 백준 2292 벌집
  • 백준 9102 괄호
오뚜깅
오뚜깅
오뚜깅
오뚜깅
오뚜깅
전체
오늘
어제
  • 분류 전체보기
    • 취업인생
    • Programming
      • C & C++
      • Python
      • OpenCV
      • PCL
      • ROS
      • Deep learning
      • Network
    • 알고리즘
      • 이론
      • 백준(BOJ)
      • 프로그래머스(Programmers)
    • Project
    • IT
      • 우분투
    • 일상
      • 말씀 묵상
      • 끄적임
      • 영어 일기

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • imageclustering
  • pointcloud
  • graphicdriver
  • installubuntu
  • C++
  • 오츠알고리즘
  • cuda설치
  • c++code
  • cudaversion
  • 백준2798
  • 딥러닝환경구축
  • pytorch
  • rospy
  • 2292
  • cuda9.0
  • installcuda
  • tensorflowversion
  • CUDA
  • OtsuAlgorithm
  • 백준2231
  • PointCloudLibrary
  • kmeansclustering
  • cv_bridge
  • clustering
  • opencv
  • DeepLearning
  • 사용자지정정규화공식
  • 우분투
  • CuDNN
  • installcudnn

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
오뚜깅
백준 2869 달팽이는 올라가고 싶다
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.