열이의 개발블로그

https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 문제 분석 N을 자기 자신보다 작거나 같은 제곱수들의 합으로 몇 개의 제곱수를 더해야 하는지 나타내는 문제 13을 예로 들면 13 = 3² + 2²이므로 2가 출력된다. 핵심은 자기 자신보다 작은 제곱수 중 가장 큰 제곱수를 빼면서 개수를 세면 된다. 하지만 가장 큰 제곱수를 뺀 뒤 또 제곱수를 찾아 빼는 연산을 반복한다면 시간 초과가 날 것이다. 다이나믹 ..

https://www.acmicpc.net/problem/1019 1019번: 책 페이지 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다. www.acmicpc.net 문제 분석 단순 N 페이지까지 반복하면서 페이지를 문자열로 변환 후 각 페이지에 존재하는 숫자만큼 등장 횟수를 누적하기가 기본적인 알고리즘일테지만 이 문제의 N의 범위는 10억 이하이기 때문에 시간 초과(시간 복잡도: O(n²))가 나오게 된다. 수학적인 접근이 필요한데 이는 백준 사이트의 최백준님의 자료를 참고하여 해결했다. 우선 각 자릿수 별로 등장 횟수를 쪼개서 생각해야 한다. 위의 자료에서는 1~N 페이지가 아닌 A~B 페이지를 기준으로 설명하였기 때문에 ..

https://www.acmicpc.net/problem/2417 2417번: 정수 제곱근 정수가 주어지면, 그 수의 정수 제곱근을 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 분석 문제 그대로 정수가 주어지면, 그 정수의 제곱근을 구하는 문제이다. n의 범위가 (0 ≤ n < 2⁶³)이므로 범위가 넓기 때문에 하나하나 다 탐색하여 제곱근을 찾기에는 시간이 부족하다. 그렇기 때문에 이분 탐색 알고리즘을 사용하여 시간을 줄여 문제를 해결하자 코드 더보기 n = int(input()) start, end = 0, n result = 0 while start

https://www.acmicpc.net/problem/4158 4158번: CD 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 상근이가 가지고 있는 CD의 수 N, 선영이가 가지고 있는 CD의 수 M이 주어진다. N과 M은 최대 백만이다. 다음 줄 www.acmicpc.net 문제 분석 상근이와 선영이가 가지고 있는 CD의 수는 각각 N, M개이며 이는 최대 1,000,000(백만)이다. 처음엔 상근이가 가지고 있는 CD와 선영이가 가지고 있는 CD를 set 자료구조를 활용하여 교집합을 구하면 풀릴 것이라고 생각하였지만 입력 범위가 커 시간 초과가 났다. 풀이 방법은 다양하겠지만 3개의 풀이 방법을 설명하려고 한다. 1. set 자료구조를 활용하여 in을 통한 개수..

https://www.acmicpc.net/problem/14264 14264번: 정육각형과 삼각형 첫째 줄에 정육각형 한 변의 길이 L이 주어진다. (1 ≤ L ≤ 1,000,000, L은 정수) www.acmicpc.net 문제 분석 위의 그림은 같이 정육각형에 각 다른 3개의 대각선을 그렸을 때 4개의 삼각형이 나오는 경우 중 가장 작은 삼각형이 최대일 때 나오는 경우이다. 빨간색으로 표시된 삼각형은 정삼각형이고 정삼각형의 넓이 공식을 이용하면 쉽게 해결할 수 있다. 코드 더보기 #include #include int main(){ double l; scanf("%lf", &l); printf("%.9lf", sqrt(3)*pow(l,2)/4); }

https://www.acmicpc.net/problem/2577 2577번: 숫자의 개수 첫째 줄에 A, 둘째 줄에 B, 셋째 줄에 C가 주어진다. A, B, C는 모두 100보다 크거나 같고, 1,000보다 작은 자연수이다. www.acmicpc.net 문제 분석 세 자리 수 세 개를 입력한 뒤 모두 곱한 후 나온 수가 0부터 9까지의 수를 몇 번씩 쓰였는지를 나타내는 문제이다. 코드 진행 방향 0부터 9까지 쓰인 개수를 담을 배열을 만든 뒤 입력받은 수들의 곱을 10씩 나누어가며 나머지를 계산해 나머지의 배열 순서에 값을 하나씩 더해준다. 코드 더보기 #include int main(){ int a, b, c, result; int arr[10]={0}; scanf("%d", &a); scanf("..

https://www.acmicpc.net/problem/10818 10818번: 최소, 최대 첫째 줄에 정수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 N개의 정수를 공백으로 구분해서 주어진다. 모든 정수는 -1,000,000보다 크거나 같고, 1,000,000보다 작거나 같은 정수이다. www.acmicpc.net 문제 분석 정렬의 문제로 보여진다. 하지만 정렬로 푸는 방법과 배열을 한 번 돌면서 최소와 최대를 골라내는 방법의 시간 차이가 조금 있었기 때문에 최소와 최대를 각각 구하는 방법으로 풀었다. 코드 진행 방향 n개의 배열을 생성한 뒤 배열을 차례로 입력받고 첫 번째로 입력받은 배열의 수를 max, min에 넣어준다. 그 후 배열의 수가 max보다 크면 max를 바..

https://www.acmicpc.net/problem/11021 11021번: A+B - 7 각 테스트 케이스마다 "Case #x: "를 출력한 다음, A+B를 출력한다. 테스트 케이스 번호는 1부터 시작한다. www.acmicpc.net 문제 분석 전에 풀었던 덧셈 문제에서 case의 번호를 앞에 출력하는 방식만 추가되었다. 코드 진행 방향 case의 수를 입력받고 A와 B를 입력한다. 그 후 Case #x: 를 출력한 뒤 A와 B의 합을 출력한다. => (Case #1: 2) case의 개수만큼 반복한 뒤 반복문을 종료한다. 코드 더보기 #include int main(){ int t; scanf("%d", &t); for(int i=1; i

https://www.acmicpc.net/problem/1110 1110번: 더하기 사이클 0보다 크거나 같고, 99보다 작거나 같은 정수가 주어질 때 다음과 같은 연산을 할 수 있다. 먼저 주어진 수가 10보다 작다면 앞에 0을 붙여 두 자리 수로 만들고, 각 자리의 숫자를 더한다. 그 다음, www.acmicpc.net 문제 분석 입력한 수의 각 자리수를 더한 뒤(10이 넘을 경우 일의 자리를 구함) 입력한 수의 일의 자리 수와 결합해 두 자리 수로 만든다. 이 방법을 반복하여 원래 입력한 수로 다시 돌아왔을 경우 과정을 몇 번 반복하는지 횟수를 출력한다. 코드 진행 방향 입력받은 수 a를 b에 저장한 뒤, b를 10으로 나눈 나머지를 temp에 저장하고 result는 각 자리수를 더한 값을 저장한..

https://www.acmicpc.net/problem/10952 10952번: A+B - 5 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. www.acmicpc.net 문제 분석 반복문을 통해 덧셈을 계속 진행하고 마지막 탈출 구문을 A와 B가 모두 0 일 때로 조건을 주어 탈출하게 한다. 코드 더보기 #include int main(){ int a, b; while(1){ scanf("%d %d", &a, &b); if(a==0 && b==0) break; printf("%d\n", a+b); } }