문제링크 : https://www.acmicpc.net/problem/1747 1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N; int arr[1003001]; void check() //소수체크 { memset(arr, 1, sizeof(arr)); arr[1]=0; //1은 소수 for(..
문제링크 : https://www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int T, a, b; int arr[10000], visited[10000]; void setting() { memset(arr, 1, sizeof(arr)); memset(visited, 0, sizeof(visited..
문제링크 : https://www.acmicpc.net/problem/2023 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N; bool check(int n) //소수 체크 { for(int i=2; i*i
문제링크 : https://www.acmicpc.net/problem/1577 1577번: 도로의 개수첫째 줄에 도로의 가로 크기 N과 세로 크기 M이 주어진다. N과 M은 100보다 작거나 같은 자연수이고, 둘째 줄에는 공사중인 도로의 개수 K가 주어진다. K는 0보다 크거나 같고, 50보다 작거나 같은 자www.acmicpc.net#include using namespace std;typedef long long ll;typedef pair pii;const int MAX = 987654321;int N, M, K, a, b, c, d;ll dp[101][101];bool check[202][202];int dy[2] = {-1, 0};int dx[2] = {0, -1};int main(){ i..
문제링크 : https://www.acmicpc.net/problem/17212 17212번: 달나라 토끼를 위한 구매대금 지불 도우미 달나라 토끼들이 사용하는 화폐는 동전뿐이다. 동전의 종류는 1원, 2원, 5원, 7원 이렇게 4종류가 있다. 물건을 사고 동전으로 계산을 하는데 동전의 개수가 최소가 되도록 지불하지 않는 것은 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, dp[100001]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> N; dp[1]=1; dp[2]=1;..
문제링크 : https://www.acmicpc.net/problem/20500 20500번: Ezreal 여눈부터 가네 ㅈㅈ 문제의 답을 $1\,000\,000\,007$로 나눈 나머지를 출력한다. www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; const int MOD = 1000000007; int N, dp[1516][3]; int func(int n, int sum, int cur) { if(n==N) { return ((!sum && cur == 5)?1:0); //3의 배수이고 끝자리가 5라면 카운팅 (15의 배수) } if(dp[n][su..
문제링크 : https://www.acmicpc.net/problem/14852 14852번: 타일 채우기 3 첫째 줄에 경우의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; const int MOD = 1000000007; int N; ll dp[1000001], sum[1000001]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> N; dp[1]=2; //N은 1인 경우 dp[2]=7; //N은 2인 경우 sum[2]=1; /..
문제링크 : https://www.acmicpc.net/problem/17845 17845번: 수강 과목 첫줄에 서윤이의 최대 공부시간 N (1 ≤ N ≤ 10,000), 과목 수 K (1 ≤ K ≤ 1,000)이 공백을 사이에 두고 주어진다. 이후 K개의 줄에 중요도 I (1 ≤ I ≤ 100,000), 필요한 공부시간 (1 ≤ T ≤ 10,000)이 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, K, result; int I[1001], T[1001], dp[1001][10001]; int main() { ios_base::sync_w..
문제링크 : https://www.acmicpc.net/problem/2228 2228번: 구간 나누기 N(1 ≤ N ≤ 100)개의 수로 이루어진 1차원 배열이 있다. 이 배열에서 M(1 ≤ M ≤ ⌈(N/2)⌉)개의 구간을 선택해서, 구간에 속한 수들의 총 합이 최대가 되도록 하려 한다. 단, 다음의 조건들이 만족되 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, M; int arr[101], dp[101][51]; int func(int n, int m) { if(m==M) return 0; //구간 선택 종료 if(n0; i--) {..
문제링크 : https://www.acmicpc.net/problem/14430 14430번: 자원 캐기 인류의 차세대 인공지능 자원 캐기 로봇인 WOOK은 인간 대신 자원을 캐는 로봇이다. WOOK은 언제나 제한된 범위 내에서 자원을 탐색하며, 왼쪽 위 (1, 1)부터 오른쪽 아래 (N, M)까지 자원을 탐색한다. www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, M; int arr[301][301], dp[301][301]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> N ..
문제링크 : https://www.acmicpc.net/problem/14606 14606번: 피자 (Small) 예제1의 입력이 1이므로, 게임 시작부터 갑이 분리할 수 있는 피자탑이 없습니다. 따라서 갑이 얻는 즐거움은 0입니다. 예제2의 정답 3은 다음과 같은 과정을 통해 얻어집니다. 먼저 놀이를 시작 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N; int dp[11]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> N; dp[1] = 0; //나누기 불가능 dp[2] =..
문제링크 : https://www.acmicpc.net/problem/19947 19947번: 투자의 귀재 배주형 2020년에 학교로 복학한 주형이는 월세를 마련하기 위해서 군 적금을 깨고 복리 투자를 하려고 한다. 주형이가 하려는 투자에는 3가지 방법의 투자 방식이 있다. 1년마다 5%의 이율을 얻는 투자 ( www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int H, Y; int dp[11]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> H >> Y; dp[0]=H; //초기비용 fo..
문제링크 : https://www.acmicpc.net/problem/15312 15312번: 이름 궁합 영어 대문자 알파벳 26개의 획수는 순서대로 3, 2, 1, 2, 3, 3, 2, 3, 3, 2, 2, 1, 2, 2, 1, 2, 2, 2, 1, 2, 1, 1, 1, 2, 2, 1 로 정한다. (출제자가 알파벳 대문자를 쓰는 방법이 기준이다) www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; string A, B; int arr[26] = {3, 2, 1, 2, 3, 3, 2, 3, 3, 2, 2, 1, 2, 2, 1, 2, 2, 2, 1, 2, 1..
문제링크 : https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, M, A, B; int inDegree[32001]; // 진입 차수 저장 vector graph[32001]; // 간선 정보 저장 vectorresult; priori..
문제링크 : https://www.acmicpc.net/problem/24447 24447번: 알고리즘 수업 - 너비 우선 탐색 4 정점 1번에서 정점 2번, 정점 4번을 순서대로 방문한다. 정점 2번에서 정점 3번을 방문한다. 정점 5번은 정점 1번에서 방문할 수 없다. 따라서, ti 값은 1번 정점부터 1, 2, 4, 3, 0이다. 너비 우선 탐색 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, M, R, cnt = 1; vectorv[100001]; ll visited[100001], seq[100001], sum=0; void bfs..