꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/2157 비교적 낮은 정답률인데도 불구하고 한번에 AC를 받아 기분 좋았던 DP 문제였습니다.현재 위치한 도시와 해당 도시가 몇 번째 방문하는 도시인지를 표시하며 메모이제이션을 하면 되는 문제였습니다.기내식을 입력받을 때 한 도시에서 다른 도시로 가는 비행기가 여러대 있을 수 있기 때문에 제일 맛있는 기내식을 제공하는 비행기를 채택하는 것이 핵심이였습니다.기저 사례는 도시를 M번 거쳤는데 N번째 즉, 도착지점에 도달 못하는 경우이고 M번 이내에 N번째 도시를 방문하면 조건이 성립됩니다.코드 자체는 어렵지 않기 때문에 코드를 보시면 쉽게 이해가 가실거라고 생각됩니다! **수정**해당 코드는 재채점 결과 틀림 처리가 되었고 새로 작성..

문제 링크입니다: https://www.acmicpc.net/problem/12894 재귀를 이용해 1번과 2번 조건을 충족시키는지 확인하는 문제였습니다. 조건 그대로 하드코딩하면 시간초과가 나기 때문에, 주어진 문자열을 s1, s2로 나눈 상태에서 s1 + s2 와 s2 + s1 중 오름차순 정렬 시 작은 문자열을 반환하면 됩니다. (lelexicographically minimum)

문제 링크입니다: https://www.acmicpc.net/problem/6571 백준 2407번 조합(http://jaimemin.tistory.com/682)에서 string을 통해 Big Integer를 구현해 봤기 때문에 문제 자체는 어렵지 않았습니다.연산자 오버로딩을 통해 string에 대해 b; if (a == "0" && b == "0") break; int cnt = 0; for (int i = 2; i < MAX; i++) if (a

문제 링크입니다: https://www.acmicpc.net/problem/3043 문제에서 요구하는 조건은 각각의 행과 열에 오직 하나의 탱크를 배치하는 것입니다.따라서, 탱크를 상하로 먼저 움직인 뒤 좌우로 움직여주면 조건을 충족시킬 수 있습니다.탱크를 움직이는 기준은 아래와 같습니다.1. 상하로 움직일 경우 y를 기준으로 정렬한 뒤 1 ~ N까지 반복문을 돌리면서 y가 해당 칸보다 아래에 있으면 위로 가야하고 해당 칸보다 위에 있으면 아래로 움직여줘야합니다.2. 좌우로 움직일 경우도 마찬가지로 x를 기준으로 정렬한 뒤 1~N까지 반복문을 돌리면서 x가 해당 칸보다 오른쪽에 있으면 왼쪽으로 가야하고 왼쪽에 있으면 오른쪽으로 움직여줘야합니다. ssangba55(https://blog.naver.com/..

문제 링크입니다: https://www.acmicpc.net/problem/2407 백준 1793번 타일링(http://jaimemin.tistory.com/618)처럼 long long 자료형의 범위를 벗어나는 답을 구해야하기 때문에 string을 통해 Big Integer를 구현합니다.조합의 경우 간단한 DP를 통해 구할 수 있기 때문에(nCr = n-1Cr + n-1Cr-1) 별도의 설명이 필요가 없습니다. #include #include #include #include //memset using namespace std; const int MAX = 100 + 1; int N, M; string cache[MAX][MAX]; string bigNumAdd(string num1, string num..

문제 링크입니다: https://www.acmicpc.net/problem/14921 백준 2470번 두 용액(http://jaimemin.tistory.com/680)과 동일한 문제였지만 용액의 합을 출력하는 문제였으므로 더 쉬운 문제였습니다. #include #include #include //LLONG_MAX using namespace std; const int MAX = 100000; int N, idx1, idx2; long long minimum; long long liquid[MAX]; long long sumOf2Liquid(void) { int i = 0, j = N - 1; while (i < j) { long long sum = liquid[i] + liquid[j]; //최소값 갱..

문제 링크입니다: https://www.acmicpc.net/problem/2470 백준 2473번 세 용액(http://jaimemin.tistory.com/679)과 동일한 방법으로 풀면 되는 문제였습니다.범위는 늘어났지만 구하는 용액의 수가 두개이니 비교적 더 쉬운 문제라고 할 수 있습니다. #include #include #include //LLONG_MAX using namespace std; const int MAX = 100000; int N, idx1, idx2; long long minimum; long long liquid[MAX]; void print2Liquid(void) { int i = 0, j = N - 1; while (i < j) { long long sum = liquid..

문제 링크입니다: https://www.acmicpc.net/problem/2473 첫 번째 용액을 기준으로 나머지 두 용액은 양방향 탐색을 통해 세 용액의 합의 최소값을 찾는 문제였습니다.사실 구현보다는 long long 자료형의 최대값을 정의하는데 애를 먹었던 문제였습니다.처음에는 numeric_limits::infinity()로 minimum을 초기화했는데 오답처리를 받아 minimum 값을 확인한 결과 0으로 초기화가 되어있었습니다.따라서, climits 헤더파일을 추가하고 minimum을 LLONG_MAX로 초기화했습니다! #include #include #include //LLONG_MAX using namespace std; const int MAX = 5000; int N, idx1, id..

문제 링크입니다: https://www.acmicpc.net/problem/2563 100 * 100 칸에서 칠해져 있는 칸의 갯수를 세면 되는 문제였습니다. #include #include using namespace std; const int MAX = 100 + 1; int coord[MAX][MAX]; int main(void){ int N; cin >> N; for (int k = 0; k > x >> y; for (int i = y + 1; i

문제 링크입니다: https://www.acmicpc.net/problem/2042 새그먼트 트리를 이용하여 푸는 문제였습니다.종만북 코드에서는 LCA(Longest Common Ancestor)를 구하는 코드이기 때문에 http://jaimemin.tistory.com/662 코드에서 조금 수정을 해야했습니다.주의할 점은, 반환형을 int가 아닌 long long으로 해야 AC를 받을 수 있다는 점입니다. #include #include #include using namespace std; int N, M, K; struct segmentTree { //배열의 길이 int n; //각 구간의 최소치 vector pSum; segmentTree(const vector &array) { n = array...