누적합을 이용하면 쉽게 풀 수 있는 문제다. sum[i]을 0~i까지의 인덱스의 모든 값의 합이라고 정의하면 for문을 돌면서 sum[i] - sum[i - x]를 구하면 x일의 모든 방문수를 확인할 수 있다. 정답 코드 #include using namespace std; int n, x, arr[250000]; int sum[250000], Max, cnt; int main(){ cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false); //input cin >> n >> x; for (int i = 0; i > arr[i]; //add sum[0] = arr[0]; for (int i = 1; i < n; i++) ..

문제푸는데 생각보다 애를 많이 먹었다. 처음에는 dp로 쉽게 풀 수 있을 줄 알았는데 n = 12일 때 arr[12] = arr[4] + arr[8] 이어야하는데 이것을 선택하도록 하는 방법을 생각해내질 못했다. 그래서 곰곰히 생각해보니 답이 1인 녀석들은 무조건 정해져있음을 알았다. i = 1 ~ 50000^(1/2) 의 수들의 제곱일 때 arr[i] = 1이다. 그러면 답이 2인 녀석들도 정해져 있다. arr[i + i] = 2이다. 그럼 답이 3인 녀석들도 정해져 있지 않은가? 답이 1인 녀석들이 i, 2인 녀석들이 j라고 하면 arr[i + j] = 3이다. (당연히 답이 2와 3 모두 될 수 있는 놈들도 있으므로 작은 것을 선택하면 된다.) 그럼 나머지 녀석들은 답이 4다. 정답 코드 #incl..

고등학생 때 한 번 쯤은 풀어봤을 법한 쉬운 경우의 수 계산 문제다. 0과 1의 개수가 1이하로만 차이나면 되기 때문에 2bits씩 묶어서 경우의 수를 계산해주면 된다. 2bits당 0과 1의 개수 차이가 1이하이려면 {01, 10} 이렇게 2개의 경우의 수가 나온다. 만일 n비트라면 n/2개의 2bits 묶음이 나오므로 총 경우의 수는 2^(n/2) 이다. 만일 n이 홀수라면 나머지 1bit가 남는데 이 1bit는 0, 1 모두 될 수 있으므로 총 경우의 수는 2^(n/2 + 1)이다. (나머지 2bits 묶음들의 0과 1의 개수 차이가 0이므로 1bit는 0, 1 모두 될 수 있음) 문제에서 16769023의 나머지를 구하라고 했으므로 모듈러 연산의 성질을 이용해 2를 곱할 때마다 모듈러 연산을 해주..

나는 처음에 수학적으로 접근하려 했다. 아니 수학적으로 접근해야 하는 것은 맞는데 나는 연립방정식을 활용해서 답을 구하려 했다. 하지만 생각보다 컴퓨터는 멍청하고, 빨랐다. 컴퓨터에게는 연립방정식의 해를 구하는 것보다 하나씩 x, y쌍을 대입하여 해를 구하는 것이 더 쉬운 방법이다. 그냥 브루트포스로 해결하자. 정답 코드 #include using namespace std; int a, b, n, w; int main(){ cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false); //input cin >> a >> b >> n >> w; //brute force int x, y, answer_cnt = 0; for (int i = 1; i

문제에 주어진 대로 계산하면 되는 쉬운 문제다. 팀별 경기 수와 득점 수, 실점 수를 나타내는 구조체를 정의하고, 이에 대한 배열을 선언하여 데이터를 관리했다. (지금 생각하니 경기 수는 저장하지 않아도 됐다) 입력을 한 줄 씩 받으면서 a팀과 b팀의 경기 수, 득점 수, 실점 수를 증가시키고, 입력이 끝나고 나면 그냥 전체 팀을 탐색하면서 피타고라스 기댓값의 최댓값, 최솟값을 갱신시키면 된다. DivisionByZero 에러가 발생할 수 있으므로 이에 대한 예외처리만 하면 딱히 신경쓸 것이 없는 문제다. 정답 코드 #include #include using namespace std; struct team{ int match = 0; int S = 0; int A = 0; }; int T, n, m; i..

아마 대부분 비슷한 문제를 풀어본 적 있었을 것이다. 이 문제의 독특한 점은 2~64진수로 표현했을 때도 회문인지 판단해야 한다는 점이다. B진법으로 변환하는 것은 어렵지 않다. 몫이 0일 때까지 나누면서 나머지를 저장하면 된다. 이 때, 저장되는 값들의 역순이 실제 B진수 값인데 우리는 회문인지 판단만 하면 되므로 굳이 역순으로 바꿀 필요가 없다. B진수를 구했으면 회문인지 판단하면 된다. 이는 그냥 for문으로 대칭되는 각 자리를 비교하면 된다. 근데 한 가지 의문이 들 수 있는데 16진수까지는 9보다 큰 수를 A, B, C, ... 으로 표현한다 치더라도 그 이상의 진법에서 뭘로 표현해야할까? 그냥 수 자체로 표현하면 된다. 예로 주어진 수가 31이고, 16진수로 변환하고자 한다면 실제 값은 1F ..