목록알고리즘 문제풀기/백준(Acmicpc) (21)
문제링크 : https://www.acmicpc.net/problem/2018 정수 N(1 연속된 수의 합이라는 점에서 등차수열을 이용했다. 5+6+7+8은 1+2+3+4+5+6+7+8에서 1+2+3+4를 뺀 값이라는 점이다. 즉, 1~8까지의 등차수열에서 1~4까지의 등차수열을 뺀 값이다. 그래서 n이라는 수를 받아서 n/2 +1까지를 탐색하며 해당 수(i)까지의 등차수열의 합이 원래의 수(N)보다 크거나 같은지를 확인한다. 그리고 크거나 같을 경우 N과의 차이를 구한다. 이렇게 구해진 N이 1~A(자연수) 까지의 등차수열의 합으로 만들 수 있는 숫자라면 i까지의 등차수열에서 A까지의 등차수열을 뺀 값이 N이라는 것을 알 수 있다. N의 최대값이 10^7이므로 더했을 때 int의 범위를 넘..
문제링크 : https://www.acmicpc.net/problem/2004 정수 n,m (0>a>>b; int c=a-b; int tempA,tempB,tempC; tempA=a; tempB=b; tempC=c; ll aCount1=0; ll bCount1=0; ll cCount1=0; // 2의 배수 ll aCount2=0; ll bCount2=0; ll cCount2=0; // 5의 배수 while(tempA>=2){ tempA/=2; aCount1+=tempA; } while(tempB>=2){ tempB/=2; bCount1+=tempB; } while(tempC>=2){ tempC/=2; cCount1+=tempC; } while(a>=5){ a/=5; aCount2+=a; } ..
문제링크 : https://www.acmicpc.net/problem/2870 줄의 개수 (1 파싱 연습을 위한 간단한 문제이다. 여기서 중요한 것은 어떻게 숫자를 뽑아낼 것인가 / 뽑아낸 숫자를 어떻게 정렬할 것인가이다. 먼저 숫자를 뽑아내는 것은 라인별로 입력을 받아서 숫자를 쌓고 있음을 의미하는 bool 변수 flag를 만든다. 숫자를 만날 경우 flag를 true로 하고 temp(string)에 숫자를 쌓는다. 그리고 문자를 만날 경우 flag를 false로 바꿔주며 숫자가 끝났음을 표시하고 만들어진 문자열(숫자)의 앞에 0을 제거해준다. (문자열의 길이를 통해 0 하나만 있을 경우 예외처리) 문자를 만나지 않았지만 라인이 끝났을 경우는 flag를 통해 확인할 수 있다. 다음으로 정렬..
문제링크 : https://www.acmicpc.net/problem/1431 기타의 개수 N( 시리얼 번호를 주어진 조건에 따라 정렬하여 결과를 출력 주어진 조건에 따라 정렬을 해야 하므로 가장 중요한 것은 조건이다. 위 내용이 그 조건이고 주어진 조건을 그대로 따라가면 되는 간단한 문제이다. 비교의 우선순위가 1 > 2 > 3이기 때문에 따라서 먼저 1번 조건을 확인한다. A와 B의 길이가 다를 때, 짧은 것이 먼저 온다. 즉, strlen을 사용해서 비교를 하라는 조건이다. 다음으로 길이가 같을 때 자리수의 합(숫자인 것만)을 비교한다. 이 과정은 매번 비교할 때마다 자리수의 합을 구하면 상당히 긴 시간이 걸릴 수 있는 과정이다. 그래서 문자열을 입력받으면서 입력받은 문자열..
문제링크 : https://www.acmicpc.net/problem/1309 우리의 크기 N(1N; for(int i=2;i
문제링크 : https://www.acmicpc.net/problem/11060 칸 수(1>n; for(int i=0;i
문제링크 : https://www.acmicpc.net/problem/10164 N(세로 사이즈, 우선 경로의 수는 int 범위 안에서 수행 가능하지만 "15 * 15밖에 안되네 그냥 int로 하자"라고 생각하면 안된다. 나중에 해보면 알겠지만 입력으로 "15 15 0"이 들어올 경우가 최다 경로인데 40,116,600개가 나온다. 18 * 18이상은 int 범위가 넘어가게 된다. [ 사이즈만 보고 방심하면 히든 케이스에서 터져버린다. 다른 문제 풀 때도 주의해야할 점 ] 이제 풀이로 들어가보면 아이디어 자체는 간단하다. 중학교 때 수학에서 배운 방법을 사용하는 것이다. 이 맵에서 1번부터 8번을 거쳐 15번까지 가는 최단경로의 수는 (1번부터 8번까지 가는 최단경로의 수) * (8번부터 1..
문제링크 : https://www.acmicpc.net/problem/14720 우유 가게 수 n n개의 가게 정보 ( 0 : 딸기우유, 1 : 초코우유, 2 : 바나나우유 ) 최대로 마실 수 있는 우유의 개수 역시 단순한 dp 문제이다. 0(딸기우유)번 가게일 경우 이전의 2(바나나우유)번 가게의 값 중 Max +1을 하고 1(초코우유)번 가게는 이전의 0(딸기우유)번 가게의 값 중 Max +1, 2(바나나우유)번 가게는 이전의 1(초코우유)번 가게의 값 중 Max +1을 하면 된다. 여기서 주의해야할 예외는 1. 맨 처음에는 딸기우유를 한 팩 마신다. 이다. 즉, 1과 2가 나오더라도 0이 나오기 전이라면 값을 갱신해서는 안된다. 예외처리를 해줘야 하는 경우는 2..