0850

옛날에 ps 공부를 조금 해두기도 했고, 가끔씩 문제를 풀기도 해서 실력 체크 겸, 동상 정도를 탈 수 있지 않을까 해서 참가하게 되었다. 결과는 4솔로 12등 마무리였다. 1~2문제는 더 풀 수 있었는데 아쉬움이 남았다. 시간 제한이 있어서 쉬운 문제도 어려워보이고, 공부할 때 제대로 안 해서 무슨 알고리즘을 써야하는 건 아는데 제대로된 구현을 못한게 컸다. 백준에 문제가 올라와서 빨리 풀 수 있는 문제만 풀어보았다. 아직 못 푼 문제도 천천히 풀 수도..? 있다. 풀이는 아래에 있다. 대회에서 푼 문제는 bold가 되어있다. (A, B, C, D) A: 인경호 울타리 공사풀이: https://wnstnk.tistory.com/25문제 그림에 힌트가 있는 0솔 방지용 문제였다. 그런데 이런 문제에 약해..

문제: https://www.acmicpc.net/problem/339272025 인하대학교 프로그래밍 경진대회 (IUPC) E번 완전탐색, 백트래킹 문제이다. 나이트가 놓일 수 있는 경우 좌표를 저장하고 모두 탐색하면 그 위치의 값들을 더한 뒤 최대인지 확인한다. x+1해주며 백트래킹을 하였고, x가 N이면 x=0, y+1해주여 다음 행을 확인하였다. m[8]배열로 나이트의 이동을 나타냈고, check함수로 그 자리에 나이트를 놓을 수 있는지 확인하였다.#include #include using namespace std;int N;pair m[8] = { {2, -1}, {2, 1}, {1, 2}, {-1,2}, {-2, 1}, {-2, -1}, {-1, -2}, {1, -2} };int map[4][..

문제: https://www.acmicpc.net/problem/339342025 인하대학교 프로그래밍 경진대회 (IUPC) K번 출발지점에서 도착지점까지 가는데 밟는 돌의 최소와 최대를 구하면 된다.최소는 쉽다. 바로 시작에서 도착 지점으로 가면 된다. 식은 다음과 같다. abs(S - E) - 1 최대는 S, E중 작은 값은 s, 큰 값을 e라 할 때, s보다 작은 번째 호수와 e보다 큰 번째 호수에서 가장 빨리 1이 나오는 두 호수를 선택하여 그 사이 돌의 수를 더하면 된다. 그림과 같이 보면 쉽다. 위 3줄은 입력 예시이고, 아래 숫자는 호수와 호수에 있는 돌들을 나타낸 것이다. 빨간 S는 시작 빨간 E는 도착이다. S, E중 작은 값은 s, 큰 값을 e라고 하면 s보다 작으면서 가장 빨리 1이 ..

문제: https://www.acmicpc.net/problem/339312025 인하대학교 프로그래밍 경진대회 (IUPC) H번 M을 N으로 나눠서 몫과 나머지가 무엇을 의미하는지 보자. 모든 체크박스는 몫만큼 클릭되고 그 중, 나머지만큼 한 번 더 클릭되는 체크박스가 생긴다. 따라서 몫이 짝수면 모든 체크 박스는 짝수 번 클릭되는데 나머지 만큼의 체크 박스만 하나 더 클릭되어서 체크가 된다. 홀수면 모든 체크 박스는 홀수 번 클릭되고 나머지 만큼의 체크박스는 짝수 번 클릭된다.ex) 8 13인 경우는 몫이 1, 나머지가 5이다. 따라서 모든 체크박스(8개)는 1번씩 클릭되는데, 나머지(5) 만큼의 체크박스는 1번씩 더 클릭된다. 따라서 8 - 5인 3개의 체크 박스만 홀수 번 클릭되어 체크 표시가 ..

문제: https://www.acmicpc.net/problem/339272025 인하대학교 프로그래밍 경진대회 (IUPC) D번 dp를 사용하여 각 격자판에 도달했을 때 가질 수 있는 최댓값과 최솟값을 각각 저장하여 다음 칸을 계산할 때 최댓값dp에서 위쪽, 왼쪽, 최솟값dp에서 위쪽, 왼쪽 총 4가지 경우를 비교하면 된다. 최댓값을 원하므로 최댓값 dp에서 (N, M) 값을 출력한다. #include #include #include #include using namespace std;typedef long long ll;int N, M;vector> v;ll map1[1001][1001];int map2[1001][1001];ll cost1[1001][1001]; //maxll cost2[1001][..

문제: https://www.acmicpc.net/problem/339252025 인하대학교 프로그래밍 경진대회 (IUPC) C번 결론부터 말하면 가장 덜 맞을 수 있는 경우의 최종 체력을 계산하고 0초과면 그대로 출력 0이하면 -1을 출력하면 된다. 장애물의 종류는 없음, 낮은 장애물, 높은 장애물, 상단 장애물로 4가지이다. 장애물이 없는 경우는 제외하고 나머지 3개의 장애물의 수를 저장한다.(s, j, jj) 각 장애물에 닿았을 경우 줄어드는 체력은 같다. 따라서 낮은 장애물이 높은 장애물보다 점프 효율이 좋기 때문에 먼저 낮은 장애물과 점프 수를 비교하여 장애물 수를 빼준다. 그 후 높은 장애물의 경우를 계산한다. 슬라이딩은 점프와 관련이 없기 때문에 아무때나 계산해준다. 마지막으로 남은 장애물..

문제: https://www.acmicpc.net/problem/339242025 인하대학교 프로그래밍 경진대회 (IUPC) B번 초기 위치만 1로 저장해둔다. 문제대로 배열 위치를 바꾸는 시뮬레이션을 구현하고 실행한 뒤, 8칸 중 1이 있는 위치를 출력한다. 대회장에서 기술A, B만 보고 위4칸, 아래4칸 배열 2개로 나누면 편하겠다 했는데, 그냥 4x2 배열 하나로 하는게 더 간단할 것 같다. #include #include #include using namespace std;int N, M, K;string st;int map1[2][2];int map2[2][2];void f(char k) { if (k == 'A') { int tmp[2][2]; for (int i..

문제: https://www.acmicpc.net/problem/339232025 인하대학교 프로그래밍 경진대회 (IUPC) A번 N과 M이 다르다면(직사각형) N과 M중 작은 값 - 1을 한 변으로 하는 정사각형이 가장 크다.N과 M이 같을 때는 그림에 힌트가 있다. (N-2)^2 + 1을 한 변으로 하는 정사각형이 가장 크다. #include #include #include using namespace std;int N, M;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> N >> M; int a; if (N != M) { a = min(N, M); ..

문제: https://www.acmicpc.net/problem/12015난이도: G2 가장 긴 증가하는 부분 수열의 길이만 구하는 문제라면 그리디한 풀이와 이분탐색으로 구할 수 있다. 모든 값에 대해 아래 과정을 반복한다. 1. vector가 비어있거나 가장 마지막 값보다 큰 수면 push_back2. vector에 있는 수라면 넘어감3. 1과 2가 아니라면 그 수보다 가장 가까운 큰 수와 대체 3을 구할 때 이분 탐색의 upper_bound로 구할 수 있다. 그리고 2는 upper_bound의 index에서 -1한 값이 같은지 아닌지 확인하면 된다.#include #include using namespace std;vector v;int main() { ios::sync_with_stdio(false..

문제: https://www.acmicpc.net/problem/7579난이도: G3 배낭문제의 일종으로 기계오리연구(https://www.acmicpc.net/problem/28082)와 유사한 문제이다.dp[i]: i의 비용으로 확보할 수 있는 최대 메모리 용량이다. N과 비용이 0~100이므로 O(100*10000)의 시간복잡도로 풀 수 있다. dp[10001]을 모두 구한 후, 그중 M 이상을 값을 가지는 비용 중 최소가 답이다. #include #include using namespace std;int dp[10001];vector a;vector m;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); in..