문제링크 : https://www.acmicpc.net/problem/2622#include using namespace std;const int MOD = 1000000007;int arr[51];int main() { int N, cnt=0; cin >> N; for(int i=1; itmp) cnt++; } } cout 삼각형의 조건은, 가장 큰 변의 길이가 나머지 두 변의 합보다 작아야 한다는 것이다.따라서 2중 반복문을 통해 가장 큰 변을 하나 고정시켜놓고, 값 조절을 통해 가능한 경우를 모두 카운팅한다.
문제링크 : https://www.acmicpc.net/problem/13251#include using namespace std;const int MOD = 1000000007;int arr[51];int main() { int M, K; int sum = 0; cin >> M; for(int i=0; i> arr[i]; sum += arr[i]; } cin >> K; double result = 0; for(int i=0; i 먼저 뽑은 조약돌이 모두 같은 색일 확률을 구하기에, 입력받은 조약돌의 모든 개수를 구해준다.그리고 기본적으로 조약돌의 개수가 K보다 작다면 아에 불가능한 케이스이기에 스킵한다. 기본적으로는 arr[i]/sum이 기..
문제링크 : https://www.acmicpc.net/problem/1124#include using namespace std;const int MOD = 1000000007;int arr[100001];bool check(int n){ if(n> A >> B; vector prime; memset(arr, 1, sizeof(arr)); for(int i=2; i 에라스토테네스의 체를 활용해 우선 입력범위 만큼 소수체크를 해준다.이때 주의할점은 j=i*i가 아니라, j=i*2로 하는 것이다.j=i*i를 하면 i 값에 따라 int 범위를 벗어나 오버플로우가 발생한다.따라서 효율성이 약간 떨어지더라도 j=i*2를 선택해주었다. 이후로는 A~B까지 각 값에 대해서 미리 판별한 소수에 ..
문제링크 : https://www.acmicpc.net/problem/9009#include using namespace std;const int MOD = 1000000007;int arr[45];int main() { int T; cin >> T; arr[0]=0; arr[1]=1; for(int i=2; i> n; vectorv; for(int i=44; i>=1; i--) { if(n 우선 피보나치 배열의 값을 채워준다.문제의 조건에 따라 n의 범위가 1,000,000,000까지 가능하므로, 44까지만 값을 채워준다. (45 : 1,134,903,170) 이후로는 뒤에서부터 체크하며 입력받은 n에 대해 arr[i..
문제링크 : https://www.acmicpc.net/problem/15353#include using namespace std;const int MOD = 1000000007;int arr[10001];int main() { string s1, s2; cin >> s1 >> s2; // 두 문자열의 길이를 맞추기 if (s1.size() = 0; i--) { int sum = (s1[i] - '0') + (s2[i] - '0') + carry; carry = sum / 10; sum %= 10; result += sum + '0'; } // 마지막 올림 체크 if (carry) result += carry..
문제링크 : https://www.acmicpc.net/problem/32981#include using namespace std;const int MOD = 1000000007;long long cal(long long base, long long exp, int mod) { long long result = 1; long long cur = base % mod; while (exp > 0) { if (exp%2) result = (result * cur) % mod; cur = (cur * cur) % mod; exp /=2; } return result;}int main() { ios::sync_with_stdio(fals..
문제링크 : https://www.acmicpc.net/problem/12871#include using namespace std;const int MOD = 1000000007;int main() { string s1, s2; cin >> s1 >> s2; string tmp1="", tmp2=""; for(int i=0; i 서로의 문자열 길이가 같은 상태에서 체크하면 되니, 다른 문자열 길이에 따라 현재 문자열을 그만큼 반복해준다.이렇게 구한 길이가 같은 문자열들에 대해 같은 지 여부 체크해주면 된다.
문제링크 : https://www.acmicpc.net/problem/11068#include using namespace std;const int MOD = 1000000007;bool isPanlindrome(int n){ for(int i=2; i> T; while(T--) { int N; cin >> N; if(isPanlindrome(N)) cout 입력받은 수에 대해서 2~64까지 각각의 진법으로 변환하여 계산하여 문자열에 저장하고,해당 문자열을 뒤집은 문자열과 비교해 같은가 아닌가를 체크한다. 같다면 1을 아니면 0을 출력해주면 된다.
문제링크 : https://www.acmicpc.net/problem/2705#include using namespace std;const int MOD = 1000000007;int dp[1001];int cal(int n){ if(n> T; memset(dp, -1, sizeof(dp)); while(T--) { cin >> N; cout 주어진 파티션에 대해 왼쪽 절반과 오른쪽 절반이 재귀적인 팰린드롬인지 체크해야한다.따라서 입력받은 n을 기준으로 절반만 체크하며 절반에 가능한 값이 있으면 대칭으로 사용이 가능하기에 가능한 가짓수를 더한다. 재귀 과정에서 시간초과 방지를 위해 이미 값이 존재하면 바로 반환해주도록 한다.그리고 기본적으로 dp[n]=1을..
문제링크 : https://www.acmicpc.net/problem/28069#include using namespace std;const int MOD = 1000000007;int main() { int N, K; cin >> N >> K; vectordp(N+1, INT_MAX); dp[0]=0; for(int i=0; i 이동 방법은 문제에 주어진 것처럼 2가지이다.(계단 한 칸 이동 or i+i/2 번째 계단으로 순간이동)따라서 해당 행동을 토대로 dp 식을 구성해준다. 먼저 dp는 최대값으로 초기화하고, 최소값을 통해 값을 갱신해나간다.이때 i+1과 i+i/2의 값이 N이 초과하지 않도록 범위를 제한해주어야 한다.둘 다 행동이 하나이므로 dp[i]+1과 비교하게 되..
문제링크 : https://www.acmicpc.net/problem/12849#include using namespace std;const int MOD = 1000000007;long long dp[8], arr[8];//정보, 전산, 신양, 진리, 학생, 형남, 환경, 미래int main() { int D; cin >> D; dp[0] = 1; // 정보과학관에서 시작 while (D--) { arr[0] = dp[1] + dp[7]; // 정보 - 전산, 미래 arr[1] = dp[0] + dp[2] + dp[7]; // 전산 - 정보, 신양, 미래 arr[2] = dp[1] + dp[3] + dp[6] + dp[7]..
문제링크 : https://www.acmicpc.net/problem/10422#include using namespace std;typedef long long ll;#define MOD 1000000007long long arr[5001];int main() { ios::sync_with_stdio(false); cin.tie(NULL); int T, N; cin >> T; arr[0]=1; //빈 문자열 for(int i=2; i> N; cout 우선 올바른 괄호 문자열은 특성상 짝수만 가능하다.그리고 구역을 2개 나눠서 생각할 필요가 있다.일단 간단하게 초기값을 알아보면 다음과 같다.N = 2()N = 4()(), (()) N = 4인 케이스를 보면,..
문제링크 : https://www.acmicpc.net/problem/1253#include using namespace std;typedef long long ll;int main() { ios::sync_with_stdio(false); cin.tie(NULL); int N, result = 0; cin >> N; vectorv(N); for(int i=0; i> v[i]; sort(v.begin(), v.end()); for(int i=0; i v[l]+v[r]) l++; else r--; } } cout 투 포인터를 활용한 문제이다.투 포인터 사용을 위해 우선 입력받은 값들을 정렬시키고 시작한다. 해당 문제에서..
문제링크 : https://www.acmicpc.net/problem/2877#include using namespace std;typedef long long ll;int main() { ios::sync_with_stdio(false); cin.tie(NULL); int K; cin >> K; K++; //2번 노드부터 시작 vectorb, v; while(K>=1) //2진수 변환 { b.push_back(K%2); K/=2; } for(int i=b.size()-1; i>=0; i--) v.push_back(b[i]); //역순 저장 for(int i=1; i 먼저 4와 7에 대해 경우의 수를 적고 규칙을 살펴보았..