[백준 24228번] 젓가락 (C++)

문제링크 : https://www.acmicpc.net/problem/24228

24228번: 젓가락

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    ll N, R;
    cin >> N >> R;

    cout << N+1 + (R-1)*2; //등차가 2인 등차수열

    return 0;
}

일단 입력받는 수의 범위가 굉장히 크므로 long long으로 선언한다.

 

그리고 예시를 하나 정하여 각 짝별로 값을 비교하여 규칙을 구했다.

N = 3 (A, B, C) 가정

 

R = 1 가정

최악의 케이스는 A, B, C를 모두 고르고 3개 중에 아무거나 골라도 1짝이 완성되기에 3 + 1 = 4이다.

여기서 A 골랐다고 가정

 

R = 2 가정

1짝일때 + 1짝을 더 추가해주면 된다.

1짝일때 고른 값과 (중복 발생), 남은 것 중 아무거나 골라도 1짝이 완성되기에 4 + 2 = 6이다.

A 선택 (중복) + B, C 중 아무거나 하나 선택 (여기서 B 골랐다고 가정)

 

R = 3 가정

2짝일때 + 1짝을 더 추가해주면 된다.

2짝일때 고른 값과 (중복 발생), 남은 것 중 아무거나 골라도 1짝이 완성되기에 6 + 2 = 8이다.

A와 B 선택 (중복), 남은 C 선택

 

규칙을 보면 2씩 증가하는 등차수열 인 것을 알 수 있다.

따라서 등차수열 공식을 이용할 수 있다.

An = A + (n-1)d

A = N+1

n = R

d= 2

 

-> N+1 + (R-1)*2