https://www.acmicpc.net/problem/19539 19539번: 사과나무 첫 번째 줄에 모든 나무가 갊자가 바라는 높이가 되도록 물뿌리개를 통해 만들 수 있으면 “YES”를, 아니면 “NO”를 따옴표를 제외하고 출력한다. www.acmicpc.net 굉장히 빠르게 풀어내서 만족스러운 문제. 일단 쉽게 관찰할 수 있는 첫번째 특징으로, 입력으로 들어온 $h_k$ 들의 합 $sum$ 이 반드시 3의 배수여야만 한다. 두 물뿌리개를 동시에 사용하면 물이 3만큼 뿌려지게 되기 때문이다. 예제 입력 4로 설명해주고 있는 또다른 조건의 하나로, 이 조건으로 인해 골드5라는 티어를 배정받지 않았나 싶다. 나무 하나를 2만큼 성장시키는 물뿌리개는 아무리 뿌려도 짝수 높이만큼의 나무를 만들 수 있기 때..

https://www.acmicpc.net/problem/2942 2942번: 퍼거슨과 사과 맨체스터 유나이티드의 감독 퍼거슨은 빨간 사과를 R개, 초록 사과를 G개 가지고 있다. 훈련장에 있는 선수들 중 몇 명에게 나누어 주려고 한다. 단, 선수들이 서로 같은 개수의 사과를 받지 못하 www.acmicpc.net 입력으로 들어오는 R과 G의 범위가 넓어서 for문으로 R,G 이하의 모든 수에 대해서 탐색하면 시간초과를 받게 될 수 있다. 시간을 절약하기 위해서 R과 G의 최대공약수를 찾아서 그 최대공약수의 약수를 찾는 방식으로 접근하면 조금 더 빠르게 풀 수 있다. R과 G가 10억에 가까운 임의의 수 두개라면 이런경우에도 TLE가 나지 싶은데 테스트케이스가 그리 빡빡하지는 않은듯..? #include..

https://www.acmicpc.net/problem/17087 17087번: 숨바꼭질 6 수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, ..., AN에 있다. 수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이 www.acmicpc.net 최대공약수를 이용하는 문제. 각 동생의 위치 $A_i$ 에 대해서 수빈이와의 거리 $dir_i$ 를 계산한다. $dir_i$ 거리를 이동하는 방법으로, 수빈이는 한번에 D만큼만 이동할 수 있기 때문에 $dir_i$ 의 약수가 D이면 수빈이가 동생을 찾을 수 있다. 가장 작은 약수는 1이므로 모든 경우에 수빈이는 동생을 찾을 수 있다. 각 $dir_i$의 약수들에 대..

https://www.acmicpc.net/problem/9527 9527번: 1의 개수 세기 두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오. 즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라 www.acmicpc.net 고민을 오래 해봐야 하는 문제 수의 범위가 크다. 일단 수의 범위가 매우 큰 편이라서, 전처리를 통해서 시간을 아낄 생각을 해봐야 한다. 대부분의 변수에서 long long 형이 필요하니까, 그냥 모든 변수 자료형을 ll으로 통일하면 깔끔해진다. cnt[k] 를 비트 k개 범위(0~2^k-1) 의 수들에서 등장하는 2진수 1의 개수의 합 으로 정의한다. 숫자 K가 i개의 ..

https://www.acmicpc.net/problem/1312 1312번: 소수 피제수(분자) A와 제수(분모) B가 있다. 두 수를 나누었을 때, 소숫점 아래 N번째 자리수를 구하려고 한다. 예를 들어, A=3, B=4, N=1이라면, A÷B=0.75 이므로 출력 값은 7이 된다. www.acmicpc.net 초등학교때의 사칙연산공부를 하던 갬성을 살려서 풀어보도록 하자. C언어의 double 형 같은 경우 정확도가 그리 높은편이 아니기 때문에 백만번 나누면 부정확해진다. python의 Decimal 형같은경우는 어찌저찌 될지도...? 근데 그것보단 아래풀이가 더 깔끔하다. 몫이 정답이 되고 나머지를 또 나눌수 있게 하기 위하여 10을 곱해주면 된다. N이 실버5치고 상당히 커보이기때문에 겁먹을 수..

https://www.acmicpc.net/problem/3049 3049번: 다각형의 대각선 세 대각선이 한 점에서 만나지 않는 볼록 N각형이 주어졌을 때, 대각선의 교차점의 개수를 세는 프로그램을 작성하시오. 아래 그림은 위의 조건을 만족하는 한 육각형의 교차점 그림이다. 모든 www.acmicpc.net 수학문제. "세 대각선이 한 점에서 만나지 않는" 이라는 조건이 중요하다. 근데 아마 지문이슈가 좀 있는거같은게 N>=3 인 N개의 대각선이 한점에서 만나지 않는 이 좀 더 정확하지 않나 싶다. 암튼 세 대각선이 한 점에서 겹치지 않는다면 대각선의 교차점이 생기는 경우는 무조건 두 대각선이 서로 한 점에서 만나는 경우인데, 대각선은 볼록 N각형의 꼭짓점에서 임의의 점 두개를 골라서 만들어 낼 수 있..