본문 바로가기

전체 글

[백준 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 더보기
[NYPC 2022년도] 후기 1일차 진척도. 480.0 1번의 난이도는 C++ 문법 조금이라도 알고, 알고리즘 공부를 1년 정도(?) 했다면 충분히 풀수 있는 문제였다. 2번은 끈기 있게 하다보면 되는 정도. 대강 구현 시도해봤는데 안됨. 3번은 세그먼트였는데 기본 문제였다고 판단된다. 1일차 총평. 대회의 취지인 코딩의 대중화에 걸맞는 문제들이었다.(1, 2, 3번 해당) 다른 문제들도 읽어 보았지만 생각할 시간이 있어야 될 것 같다. 상위 50위 안에 들고 싶다. 2일차 진척도 548.2 (548.2-480=68.2) 2일 차에는 잠이 너무와 일찍 잤다. 때문에 진척도가 많이 없어 보인다. 2번 문제를 다 먹고 8번 문제를 조금 먹었다.(규칙이 있음) 5번 문제(달팽이)를 푸는 방법을 생각 해내었고(이분탐색) 4, 7, 8번의 .. 더보기
[2022년도 NYPC] 변경된 규칙에 대한 간단한 후기 서론 이번 NYPC는 작년과 다른 시스템이 생기게 되었다. 커트라인 제도 일주일이라는 긴 시간 동안 대회와 학업을 병행하니 부담이 되었는데, 이번 년도에는 커트라인이라는 개념이 생겨서 비교적으로 안정감을 느끼게 되어 학업과 대회를 병행하는데에 부담이 덜할 것으로 보인다. 이러한 제도가 있으면 "250점만 넘기면 그만이야!!"라는 사람도 생길 것 같은데 상위50명+추첨50명(문제를 많이 풀면 확률 증가), 총 100명의 참가자 한테 굿즈를 증정한다고 하니 위 같은 부작용을 고려한 것이 느껴진다. 1일차에 모든 문제 공개 작년에는 조금씩 문제를 발표했는데 '구지?'라는 생각이 들었는데 이렇게 개편이 되니 개인적으로 좋은 것 같다. ROUND제 위에서 말했던 것처럼 저번에는 1주일 동안 예선을 치르어서 학업과.. 더보기
[백준 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(.. 더보기

티스토리툴바