본문 바로가기

코딩/PS

[백준 1520] 내리막 길 / C++ 1520번: 내리막 길 (acmicpc.net)] 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 문제 이해 1. 세준이는 좌표평면 (0, 0) 에서 (n-1, m-1)까지 가는 경우의 수를 구해야 한다. 2. 세준이는 자신이 있는 곳의 높이보다 작은 높이인 좌표로 이동가능 하다. 2-1. 높이가 낮은 곳이 아니면 이동 못하다.(높이가 같은 곳도 이동 못함) 기본 아이디어 : 최단 거리로 이동하는 경우의 수 그냥 중고등학교 때 경우의 수 문제 풀면서 보는 기초 문제이다. 이것을 보면 이해가 될 것 이다. 경우의 수.. 더보기
[백준 1110] 더하기 사이클 / 증명 1110번: 더하기 사이클 (acmicpc.net) 1110번: 더하기 사이클 0보다 크거나 같고, 99보다 작거나 같은 정수가 주어질 때 다음과 같은 연산을 할 수 있다. 먼저 주어진 수가 10보다 작다면 앞에 0을 붙여 두 자리 수로 만들고, 각 자리의 숫자를 더한다. 그 다음, www.acmicpc.net 문제 요약 a=a/10*10+(a/10+a%10)%10을 계속 반복하여 a의 값이 처음 입력했던 값과 같아질 때의 최소 연산횟수를 구하는 것이다. 증명 1. a->b 일때, b에 대한 a은 특정 된다. a가 A*10+B로 이루어져 있을 때 b는 B*10+C로 이루어져 있다. C는 (A+B)%10이다. (현재 B와 C를 알고 있는 상태, A는 모름) A값에 따른 C의 값은 C(x)=(x+B)%10 .. 더보기
[NYPC 2022년도] 카트라이더 보드게임 / 2번 문제 문제 난이도 / 7시간 투자? 득점 / 200점 풀이 디피 시뮬레이션으로 구현 가능하지만 나는 노가다를 하였다. 하다보면 규칙이 보인다. 1. 한 바퀴를 돌 때 최대 득점을 갖는 방법을 가장 근접한 횟수에 맞게 복붙을 한다. 2. 도착지점에 도착한다. 이 두 과정을 유도리있게 사용한다면 풀리더라.. 더보기
[NYPC 2022년도] 인류의 적 모기 퇴치 / 1번 문제 난이도 / 백준 티어 실버 이하 득점 200점 풀이 모든 좌표에서 + 형으로 검사를 하고, x 형으로 검사를 한다. 코드 #include using namespace std; int a[100][100], n, m; int x2[4]={1, 1, -1, -1}; int y2[4]={1, -1, -1, 1}; int x3[4]={1, 0, -1, 0}; int y3[4]={0, -1, 0, 1}; int k(int x, int y) { int P=a[x][y]; for(int j=0; j 더보기
[백준 1050] 물약 1050번: 물약 (acmicpc.net) 알아야 하는 것 STL : map, min(int, int) 이 것만 알아도 풀 수 있다. 생각해야할 것 이 문제는 생각할 것들이 많은 문제였다. 그에 대한 질문을 모아놓았길래 이를 토대로 한번 포스팅 해볼려고 한다. 글 읽기 - 1050 포션 문제를 풀던 도중 경우의 수에 대해 질문드립니다. (acmicpc.net) 글 읽기 - 1050 포션 문제를 풀던 도중 경우의 수에 대해 질문드립니다. 댓글을 작성하려면 로그인해야 합니다. www.acmicpc.net 나는 이 질문에서 4, 5번 이 생각할 만한 것 같은 것 같다.(나머지는 고려하지 문제 푸는데 의미는 없을 듯/ 괜한 걱정) 1.판매도 하고 조합도 되는데 조합 단가가 더 싼 품목 A=10 B=1 A=1B .. 더보기
[백준] 트리의 지름(1967번) 1967번: 트리의 지름 (acmicpc.net) 문제 요약 트리에서 가장 멀리 떨어진 두 노드 사이의 길이를 구하시오. (단, 루트 노드는 1이다.) 아이디어 한 노드에서 자식 노드까지의 거리 가장 큰 2개를 더하여 그 최댓값을 구한다. 풀이과정 이러한 형태의 트리가 있을 때 트리의 깊이를 알 수 있다. 깊이가 가장 깊은 것 부터 연산하여 자신의 부모 노드에 간선의 가중치+max(D[그 노드의 번호]) 를 기억한다. D[6]=D[7]+15, D[6]=D[8]+4, D[6]=D[9]+9 로 D[6]에는 {15, 9, 4, 0}이 기억되어 있다. (0은 초기값) 이러한 연산을 계속한다면 D의 값은 이러할 것이다. 그러면 K에 D안에 값들의 최대값 2개를 더하는 연산을 한다.(K초기값 : -1) K=max(.. 더보기

티스토리툴바