본문 바로가기

프로그래밍/PS

 (80)
[C++] 백준 2206번: 벽 부수고 이동하기 풀이 과정 오답: 시간초과(2%) 더보기 #include using namespace std; #define TC(T) int T; cin >> T; while(T--) #define FAST_IO cin.tie(NULL); ios::sync_with_stdio(false); #define FOR(i, N) for(int i = 0; i > N >> M; vec..
[C++] 백준 10757번: 큰 수 A + B 풀이 C#에서는 BigInteger 클래스로 하면 뚝딱일 수 있지만 문제 출제의도에 벗어나기 때문에 C++로 하는 것이 바람직하다. 나는 두 큰 수를 string으로 입력받은 후 각 숫자 배열을 역순으로 해줬다. 그리고 정답을 담을 int형 리스트를 만들었다. 두 수의 각 자리별로 수를 더하고 결과의 십의 자리는 올림처리를 해주고 일의 자리를 리스트에 추가한다. 짤은 수의 끝까지 그렇게 계산하면 마지막 계산에서의 올림이 남을 수 있다. 이제 긴 수의 나머지 부분의 각 자리별로 올림처리를 계속 해주며 리스트에 추가한다. 마지막으로 남은 올림처리까지 해주면 끝. 두 수를 string으로 입력 받았기 떄문에 각 자리수가 0이 아닌 '0'처럼 저장된 것에 유의해야한다. 코드 #include using names..
[C++] 백준 14502번: 연구소 첫 번째 시도 0인 칸 중 세 칸을 골라 1로 만드는 모든 경우를 저장한다. 그 경우를 모두 순회하며 2인 칸부터 시작하여 너비 우선 탐색을 진행한다. 인접한 칸이 0인 칸을 2로 만들어가며 너비우선탐색을 마치면, 0인 칸의 수를 세어 최대값을 찾는다. 더보기 #include using namespace std; #define TC(T) int T; cin >> T; while(T--) #define FAST_IO cin.tie(NULL); ios::sync_with_stdio(false); #define FOR(i, N) for(int i = 0; i < N; ++i) #define INF 987654321 #define ERR 1e-13 #define EL "\n" int main() { #ifdef..
[C++] 백준 9465번: 스티커 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 풀이과정 \(i\)번째 열까지의 최대값을 차례로 찾는 것이 관건이다. 위와 아래의 스티커 중 어떤 것을 선택하는 것이 이후에 최대값을 만드는데 유리한지 모르므로, 각 경우에 따라 최대값을 저장해야 한다. \(i\)번째 열까지의 최대값을 구하면 아래와 같다. \(\text{if i is 0 then, }\) \(\text{ }score[i][0] = sticker[0][0]\) \(\te..
[C++] 백준 2193번: 이친수 문제 바로가기 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 풀이 과정 길이가 \(i-1\)일 때, 0으로 끝나는 이친수의 수를 \(\text{number_of_zeros}_{i-1}\), 1로 끝나는 이친수의 수를 \(\text{number_of_ones}_{i-1}\)이라고 하면 $$\text{number_of_zeros}_{i} = \text{number_of_zeroes}_{i-1}+\text{number_of_ones}_{i-1}$$ $$\text{number_of_ones}_{i} = ..
[C++] 백준 6986번: 절사평균 풀이과정 1. 수열을 벡터로 입력받고, STL sort 함수로 정렬한다. 2. 절사평균은 \(\frac{\sum_{i=K}^{N-K-1}{arr[i]}}{N-2K}\)의 값을 출력한다. 3. 보정평균은 \(\frac{arr[K]\times{K}+arr[N-K-1]\times{K}+\sum_{i=K}^{N-K-1}{arr[i]}}{N}\)의 값을 출력한다. 주의사항 1. 벡터의 형식은 double이다. 2. 출력할 때, 다음과 같이 해야 소숫점 아래 3번째 자리에서 반올림을 하여 표시된다. 뿐만 아니라 소숫점 아래 2번째 자리까지의 표시가 고정된다. cout.precision(2); cout > T; while(T--) #define FAST_IO cin.tie(NULL); ios::sync_with_st..
[C++] 백준 1025번: 제곱수 찾기 https://www.acmicpc.net/problem/1025 1025번: 제곱수 찾기 첫째 줄에 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 직사각형 격자판에 쓰여 있는 수가 주어진다. 모두 한자리이다. N과 M은 9보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 문제 문제 설명이 어렵게 서술돼 있다. 주어진 N x M의 격자판에서 행 번호와 열 번호가 각각 등차수열을 이루는 제곱수 중 가장 큰 값을 구하는 것이 목표다. 예를 들어, {arr[0][0], arr[1][2], arr[2][4]} 처럼 행 번호는 공차가 1인 등차수열이고 열 번호는 공차가 2인 등차수열인 경우가 있다. 이때, 각각의 수가 {1, 2, 1}일 경우 이는 제곱수이므로 후보가 될 수..
[C++] 백준 11660번: 구간 합 구하기 5 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 풀이과정 1. 아래 표에서 \((0,0)\)부터 \((i, j)\)까지의 합은 다음 식으로 구할 수 있다. $$ S(i, j) = A(i, j) + S(i, j - 1) + S(i - 1, j - 1) - S(i - 1, j - 1)$$ 2. 아래 그림에서 초록색 칸을 모두 더하고 주황색 칸을 모두 뺀 값이라고 생각하면 된다. 3. \((r_1,c_1)\..

티스토리툴바