본문 바로가기

분류 전체보기

 (58)
백준 15559 내 선물을 받아줘 http://www.acmicpc.net/problem/15559 15559번: 내 선물을 받아줘 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000, 1 < N×M ≤ 1,000,000) 둘째 줄부터 N개의 줄에는 구사과가 있는 곳의 지도가 주어진다. 지도에 쓰여 있는대로 이동했을 www.acmicpc.net 그래프 탐색 문제입니다. NXM 격자에 각자 그 칸에서 가야만 하는 방향이 적혀있는데 최소의 선물을 둬서 어떤 칸에 있더라도 선물이 있는 칸으로 갈 수 있게 하는게 문제입니다. 이는 유향 그래프의 연결요소를 구하는 문제와 동일합니다. 모든 칸에 대해 그래프 탐색을 시행하여 방문했던칸들에 대해서는 선물을 두지않고 방문했던 칸에 대해서 선물을 두면 됩니다. 이..
SCPC 2022 예선 1라운드 후기 SCPC를 대학교 4학년동안 처음 참가해봤습니다. 그전에 들었던 얘기로 솔브드 티어로 골드~플레정도로 나온다고 들었는데 요구하는 아이디어들이 생각보다 어렵더라고요.. 간신히 2솔했습니다. 다른 문제들의 서브태스크들을 긁어보려했는데 잘안됐습니다. ㅜ 1번문제는 단순 정렬문제라 쉽게 풀수 있었습니다. 솔브드 티어로 치면 실버2~실버1정도인것 같습니다. 어떤 좌표가 가야할 최종 좌표는 정해져있으므로 정렬후 목표인 좌표와 현재좌표를 단순히 빼면 되는 문제였습니다. 2번문제는 아이디어가 필요한 문제였습니다. 수열을 똑같은 합을 가진 K개의 그룹으로 나누는 경우의수를 찾는 문제였습니다. 따라서 수열의 총합/K가 그룹의 합이 될것입니다. 수열의 총합/K로 그룹의 합을 구하지 못하는 경우가 있는데요. 바로 수열의 총합..
백준 2069 보이는 산맥 (C++) http://acmicpc.net/problem/2069 2069번: 보이는 산맥 첫째 줄에 N이 입력된다. 둘째 줄부터 N+1번째 줄까지, 각각의 줄에는 산 하나를 표현하는 왼쪽 꼭짓점의 x좌표, 아래쪽 꼭짓점의 x좌표가 공백을 사이에 두고 입력된다. 입력으로 주어지는 x좌표 www.acmicpc.net 정렬을 이용해 푸는 문제 였습니다. 입력으로 주어지는 산의 x좌표 두 개를 우리는 1차원 좌표위에 선분으로 생각 할 수 있습니다. 따라서 선분의 양 끝 좌표가 주어질때 겹치는부분을 제외한 선분의 총 길이를 구하는 것과 유사하다고 볼 수 있습니다. 그렇게 바꿔서 생각하면 문제가 훨씬 쉬워집니다. 먼저 선분의 왼쪽 좌표에 대해 정렬을 합니다. 어떤 선분을 탐색할때 그 선분의 왼쪽 좌표보다 왼쪽에서 시작하는..
백준 1994 등차수열 (C++) https://www.acmicpc.net/problem/1994 1994번: 등차수열 N개의 음 아닌 정수들이 있다. 이들 중 몇 개의 정수를 선택하여 나열하면 등차수열을 만들 수 있다. 예를 들어 4, 3, 1, 5, 7이 있을 때 1, 3, 5, 7을 선택하여 나열하면 등차수열이 된다. 이와 같이 www.acmicpc.net map을 이용한 dp문제였습니다. 처음에 키값을 pair형태로 사용하려해서 메모리초과가 계속 나 애를 많이 먹었습니다. 앞으로는 map에 들어가는 데이터가 많을때는 키값을 pair로 두기보다 배열형태로 pair 값 하나를 대체하는게 낫다는걸 깨달았습니다. 수열과 똑같은 크기의 배열을 만들고 각 index마다 공차를 키값으로 바텀업 dp를 하면 됩니다. #include #incl..
백준 3678 카탄의 개척자 (C++) https://www.acmicpc.net/problem/3678 3678번: 카탄의 개척자 "카탄의 개척자"는 많은 사람들이 즐기는 보드게임이다. 게임을 시작하려면, 먼저 게임판을 랜덤으로 만들어야 한다. 게임판은 육각형 타일로 이루어져 있으며, 각 타일은 자원을 하나씩 포함하 www.acmicpc.net 육각형 모양의 경로를 생각해야하는 시뮬레이션 문제였습니다. 초기값 1을 넣어준후 주변 육각형 둘레로 감싸는 부분을 고려해서 풀었습니다. 바깥 육각형이 안쪽 육각형과 접하는 부분을 알아내야 하는데 저는 경로 순서를 좌표로 두고 각각 육각형의 변이 1씩 커지는걸 이용해서 안쪽과 바깥쪽 육각형 관계를 구했습니다. 육각형의 마지막을 이루는 타일은 첫 타일과 마주하므로 이에 주의하면 됩니다. #include ..
백준 1744 수 묶기 (C++) https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 우선순위 큐를 이용하는 문제였습니다. 직관적으로 마이너스큰수끼리 곱하고 양수 큰수끼리 곱하면 된다는걸 알 수 있습니다. 우리가 생각해야할것은 1과 어떤수를 곱하는것보다 1과 어떤수를 서로 더하는게 낫다는것과 음수끼리 서로 곱하고 1개 남았을때는 0이 남았을경우 0과 남은 음수1개를 곱하는게 좋다는 것입니다. 우선순위 큐를 통해 양수와 음수 큰수끼리 2개씩 뽑아서 곱한 후 남은 수를 전부 우선순위..
백준 23325 마법천자문 (C++) https://www.acmicpc.net/problem/23325 23325번: 마법천자문 최근最近 만화漫畫 마법천자문魔法千字文을 감명感銘 깊게 읽은 연두然斗는, 모든 수數를 한자漢字로 적기 시작始作했다. 그런데 수업授業을 들으면서 필기筆記 해놓은 내용內容을 복습復習 www.acmicpc.net dp의 정석적인 문제였습니다. '+' '-' '+-'인 경우가 수가 되고 '+' '-'는 연산자가 될 수 있습니다. 현재 문자를 input[x]라 하면 input[x]와 input[x-1]은 '-' 아니면 '+'이므로 input[x]는 수가 될수있고 input[x-1]은 연산자가 될 수 있습니다 따라서 (x-2까지의 연산결과 최대값(수)) input[x-1](연산자) input[x](수) 인 경우와 (x-3까지..
백준 10838 트리 (C++) https://www.acmicpc.net/problem/10838 10838번: 트리 N개의 노드로 구성된 루트가 있는 트리가 다음과 같이 주어진다. 각 노드는 0부터 N-1까지의 번호로 구별되고, 0번 노드는 루트 노드이고, 나머지 노드 각각은 0번 노드의 자식 노드이다. 트리에 www.acmicpc.net lca를 이용하는 문제입니다. level을 맞추는 lca를 사용해서 처음 풀었는데 시간초과가 났습니다. 문제에 힌트가 있는걸 처음에 놓쳤습니다. 질의에 사용되는 "노드 간의 거리는 1000이하" 를 통해 level을 맞추지 않아도 되는걸 느꼈습니다. 이번 문제에서 느낀건 변경되는 트리에서 level을 바꾸는 작업은 시간이 많이드는 작업이라는 것이었습니다.(subtree 개수가 커질 수 있으므로) ..

티스토리툴바