알고리즘/백준(131)
-
[백준 2455번] 지능형 기차
풀이한 정거장에 설때마다 탄사람을 플러스, 내린사람을 마이너스 해주면서 4개의 정류장만 거치면된다.대신 각 정류장에 거칠때마다 최대값을 비교해주면 해결할 수 있다. 소스코드123456789101112131415#include using namespace std; int main() { int Max=0,sum=0; for (int i = 0; i > minus >> plus; sum += plus; sum -= minus; if (sum > Max) { Max = sum; } } cout
2017.06.30 -
[백준 2167번] 2차원 배열의 합
풀이다중 포문을 이용해서 범위내에 있는 배열의 원소의 합을 구해도 풀 수 있다. 소스코드12345678910111213141516171819202122232425#include using namespace std; int main() { int n, m, num[301][301],k; cin >> n >> m; for (int i = 0; i num[i][j]; } } cin >> k; for (int a = 0; a > i >> j >> x >> y; for (int start = i - 1; start
2017.06.30 -
[백준 5014번] 스타트링크
풀이재귀로 풀려고 했지만 크기가 커서 스택 오버플로우를 맞이할 수도있겠다는 생각이 들었다. --> 메모이제이션을 사용하면 풀수도 있을것같다. 갈수 있는 방법을 모두 가되 중복되지 않게 이동하는 하는 방법에 대해 생각해보면 BFS를 통해 풀수있다는 것을 알 수 있었다. 현재 층에서 아래로 갔을 경우, 위로 갔을 경우 큐에 삽입해두고, 하나씩 꺼내면서 목표한 층이 맞는지 비교해보면 된다. 소스 코드12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#include using namespace std;// f -> 전체 층수// s -> 현재 층// g -> 가..
2017.06.25 -
[백준 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