[BOJ] AC그룹 모의대회2 풀이 - 1

- 목차

1. 설명

2. 문제 리스트

3. 각 문제 풀이 및 개선할 점, 코드

 

1. 설명

22-10-30 21:00:00~ 23:00:00 2시간동안 진행한 모의대회 2 관련 풀이 정리

https://www.acmicpc.net/group/practice/view/15679/17

로그인

2. 문제 리스트

• A - 제곱수의 합 (solved)
• https://www.acmicpc.net/problem/1699
• B - 골드바흐의 추측 (solved)
• https://www.acmicpc.net/problem/6588
• C - 기상청 인턴 신현수 (solved)
• https://www.acmicpc.net/problem/2435
• D - 수열의 구간 평균
• https://www.acmicpc.net/problem/19566
• E - 공백 없는 A+B (solved)
• https://www.acmicpc.net/problem/15873
• F - LOL
• https://www.acmicpc.net/problem/11140
• G - 3으로 나누어 떨어지지 않는 배열
• https://www.acmicpc.net/problem/2938
• H - 단어 뒤집기 2 (solved)
• https://www.acmicpc.net/problem/17413

3. 각 문제 풀이

---

• A - 제곱수의 합
• https://www.acmicpc.net/problem/1699

1699번: 제곱수의 합

문제

자연수 n이 주어졌을 때, 그 수를 표현할 수 있는 가장 작은 개수의 제곱수의 합을 출력하면 되는 문제이다.

ex) n = 11이면 11 = 3^2 + 1^2 + 1^2 -> 3개 -> output : 3

 

해결 아이디어

dp를 이용해 해결했다.

배열을 하나 만들고, 각 칸에서는(i번째) 인덱스를 나가지 않는 범위 한에서 현재 칸의 1, 4, 9, 16, 25, .. 번째 전의 칸에 담겨져 있는 수 + 1을 한 값들 중 가장 작은 값을 저장한다.

pivot = 1;
while (i - pivot * pivot >= 0) {
    if (memory[i] < 0 || memory[i] > memory[i - pivot * pivot] + 1) {
        memory[i] = memory[i - pivot * pivot] + 1;
    }
    pivot++;
}

개선할 점

처음엔 dfs로 가장 큰 제곱수부터 빼주는 방식을 생각했지만, 이내 11의 제곱수의 개수는 10, 9까지의 수를 표현하는 제곱수의 개수에서 얼마만큼을 더해 주어 표현할 수 있다는 것을 떠올리고, dp 풀이를 만들어낼 수 있었다.

코드

 

---

• B - 골드바흐의 추측
• https://www.acmicpc.net/problem/6588

6588번: 골드바흐의 추측

문제

골드바흐의 추측이란, 4 이상의 짝수는 두 홀수 소수의 합으로 나타낼 수 있다는 것이다.

백만 이하의 짝수에 대해 골드바흐의 추측이 성립하는지, 만약 성립한다면 n = a + b 꼴로 정답을 출력한다.

만약 답이 여러개라면, b - a가 가장 큰 case 하나만 출력한다.

만약 성립하지 않는다면, "Goldbach's conjecture is wrong." 을 출력한다. 그럴 일은 없겠지만.

해결 아이디어

홀수 판정 함수를 이용해 (여기서는 간단하게 sqrt(n)까지만 체크해주는 함수 사용해도 n <= 10^6까지이므로 시간초과는 안남) 풀었다.

i를 3부터 반복하면서(가장 작은 홀수 소수), 만약 i와 n - i 모두 소수라면 정답을 출력한다. (이러면 b - a가 최대가 되는 경우를 가장 먼저 찾음.)

개선할 점

for문에서 i++대신 홀수만 체크하므로 i += 2 를 적었어야 했다. (4 이상은 소수가 아니므로 넘어갔음)

소수판정 방식을 에라토스테네스의 체 알고리즘을 이용하면 더 빠르게 소수를 판정해낼 수 있다.

코드

 

---

• C - 기상청 인턴 신현수
• https://www.acmicpc.net/problem/2435

2435번: 기상청 인턴 신현수

문제

n 길이의 배열에서 k개의 연속된 숫자의 합들 중 최댓값을 찾아내면 되는 문제이다.

해결 아이디어

이중 반복문을 사용해 n - k + 1번의 반복 루프에서 각각 k번 합을 구해 최댓값과 비교하는 풀이를 작성했다.

개선할 점

누적합 방식이나 세그먼트 트리를 사용하면 O(1)만에 구간합을 구할 수 있다.

이를 풀면서 떠올리지는 못했지만, 더 어려운 문제를 풀때는 구간합이나 세그먼트 트리를 사용하자.

코드

---

• D - 수열의 구간 평균
• https://www.acmicpc.net/problem/19566

19566번: 수열의 구간 평균

문제

아직 해결하진 못한 문제이다.

해결 아이디어

코드

---

• E - 공백 없는 A+B
• https://www.acmicpc.net/problem/15873

문제

자연수 A, B가 AB형태의 연속된 문자열로 주어질 때 (A, B <= 10) A + B값을 구하는 문제이다.

해결 아이디어

A, B가 하나라도 10인 경우를 제외하면, 그냥 십의자리와 일의자리를 출력하고,

만약 둘 중 하나가 10이라면

A가 10이고 B는 일의 자리일때 - 3자리가 나오고 일의자리 != 0이므로 B = A % 10으로 저장하고, A /=10을 하여 A + B값을 출력한다.

A가 일의 자리이고 B는 10일때 - 3자리면서 일의자리 == 0이므로 B = 10, A /=100을 하여 정답을 출력한다.

A, B 모두 10일때 - 4자리면 20을 출력한다.

코드

---

• F - LOL
• https://www.acmicpc.net/problem/11140

문제

아직 해결하지 못한 문제이다.

해결 아이디어

코드

---

• G - 3으로 나누어 떨어지지 않는 배열
• https://www.acmicpc.net/problem/2938

문제

아직 해결하지 못한 문제이다.

해결 아이디어

코드

---

• H - 단어 뒤집기 2
• https://www.acmicpc.net/problem/17413

17413번: 단어 뒤집기 2

문제

<> 안에 있는 문자열은 '태그' 라고 부르고, 그 외의 문자열은 '단어'라고 부르며 공백으로 구분한다.

이때 입력받은 문자열에서 단어들만 반대로 뒤집어 결과를 출력한다.

해결 아이디어

mode로 태그 안일때, 밖일 때를 나누어 안일때는 >이 나올 때까지 i를 증가시키고, 밖일 때는 ' '(공백)이 나오거나, '<'꺾쇠를 만나거나 문자열이 끝나면 이제까지 입력받았던 문자열을 뒤집은 결과를 현재 문자열에서 replace한다.

코드

---