알고리즘(139)
-
[코드그라운드] 부분배열
소스코드123456789101112131415161718192021222324252627282930313233343536373839404142#include using namespace std; int Answer; int main(int argc, char** argv){ ios::sync_with_stdio(false); int T, test_case; cin >> T; for (test_case = 0; test_case > n >> s; for (int i = 0; i > num[i]; } long long sum = 0; while (1) { if (left > right || right > n) { break; } else if (sum = s) { Answer = (Answer>(right ..
2017.06.23 -
[백준 2644번] 촌수계산
풀이BFS 문제인데 촌수(카운트)를 세줄때 cnt_que를 생성해서 계산해주어야 해결가능했다... 소스 코드123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#include using namespace std; int n, m, dest_x, dest_y, xy[101][101] = {0,};int q[10001], head = 0, tail = 0,flag=0,result;int cnt_q[10001], c_head = 0, c_tail = 0;void push(int a) { q[tail++] = a;} void c_push(int a) { c..
2017.06.23 -
[백준 9461번] 파도반 수열
풀이식을 순서대로 쭉써보면 점화식을 얻을 수 있다. 주어진 삼각형 예시를 보면서 작성하면 다음과 같은 식을 얻을 수 있었다. 1234dp[6] = dp[1] + dp[5];dp[7] = dp[2] + dp[6];dp[8] = dp[3] + dp[7];dp[9] = dp[4] + dp[8];cs 1번~5번까지는 딱히 규칙을 찾을 수 없지만 이후에는 규칙을 찾을 수 있다. 여기서 n=100을 입력했을 때 값의 범위를 넘어가므로 int형으로는 표시할 수 없음만 조심하면 된다. 소스 코드1234567891011121314151617181920#include using namespace std; int main() { int n, tc; long long dp[101]; cin >> tc; while (tc--)..
2017.06.20 -
[백준 11057번] 오르막 수
풀이 1일 때 -> 0 1 2 3 4 5 6 7 8 92일 때 -> 01 02 03 04 05 06 07 08 09 12 13 14 15 16 17 18 19 23 24 25 26 27 28 29 : 78 79 893일 때 -> 001 002 003 004 005 006 007 008 009 012 013 014 015 016 017 018 019 : 779 789 889 규칙1 -> 102 -> 10 + 9 + 8 + 7 + ...... + 3 + 2 + 1 = 553 -> 55 + 45 + 36 + ...... + 1 = 220 하나씩 증가할수록 이전에 계산한 총합부터 계산해야한다. 10007으로 나눈 나머지를 계산해야 하므로 숫자가 커지게되면 %10007을 해주어야 한다. 소스 코드123456789..
2017.06.16 -
[백준 1212번] 8진수 2진수
풀이숫자의 크기가 아닌 수의 길이가 333,334를 넘지 않다고 했으니 수를 입력받을때 int형으로 받을 수 없다.string 라이브러리를 이용해서 풀수있다. 소스코드123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include #include using namespace std; string trans(char a) { string result; if (a == '0') result = "000"; else if (a == '1') result = "001"; else if (a == '2') result = "010"; else if (a == '3') result = "011"; else i..
2017.06.15 -
[백준 11048번] 이동하기
풀이조건은 딱 세가지 경우이다.1. 오른쪽으로 한칸2. 아래로 한칸3. 대각선 남동쪽으로 한칸 이 세가지 경우중 합이 가장 큰값을 찾아서 DP방식으로 풀어내면 가능하다. 재귀로 푸려고 했지만 2차원 배열에서 재귀로 풀면 시간초과가 나는 경우가 많아 DP로 시도했다. 소스코드1234567891011121314151617181920212223242526272829303132333435363738394041424344#include using namespace std; int n, m, map[1001][1001];int tmp_arr[2][1001]; int Max(int a, int b) { return a > b ? a : b;} int main() { cin >> n >> m; for (int i = ..
2017.06.15