c104 [백준/C,C++] 7562번: 나이트의 이동 www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 풀이 최단 거리를 찾는 문제이기 때문에 전형적인 BFS 문제라고 볼 수 있습니다. 가장 기본적인 2차원 배열 위에서 상하좌우로 이동 가능한 미로 문제 등과 달리 나이트가 이동 가능한 8방향으로 이동하며 탐색합니다. 역시나 depth를 계산해 주면 되는 문제고 특별히 어려운 점은 없습니다. #include #include #include #define py first #define px second using na.. 2021. 4. 21. [백준/C,C++] 1406번: 에디터 www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 풀이 리스트를 통해 구현할 수 있는 문제입니다. 처음에 단순히 string 배열을 통해 구현했었는데 문자열이 복사되는 과정에서 시간을 많이 잡아먹어 시간 초과가 났었습니다. #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); string s; int .. 2021. 4. 21. [백준/C,C++] 2812번: 크게 만들기 www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 스택을 이용해 풀 수 있는 문제입니다. 219879가 입력되었고, 지워야 할 숫자가 3개라고 생각해봅시다. 먼저 첫 번째 자릿수인 2를 스택에 push 합니다. 이후부터 각 자릿수를 탐색하며 스택에 push 되어있는 숫자를 비교합니다. 만약 탐색 중인 자릿수의 숫자가 스택에 push 되어있는 숫자보다 크다면 스택의 숫자를 pop 해주며 k를 감소 시켜 줍니다. 즉 현재 지워야 할 숫자가 남아있고, 이전 자릿수들의 숫자가 현재 자릿수의 숫자보다 작다면 지워주는 것입니다. 219879의.. 2021. 4. 20. [백준/C,C++] 1049번: 기타줄 www.acmicpc.net/problem/1049 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주 www.acmicpc.net 풀이 살짝 헷갈리는 문제입니다. 경우를 잘 따져야 하는데요.. 크게 2가지로 나눌 수 있습니다. 패키지 가격보다 낱개 6개의 가격이 더 낮은 경우, 낱개로 모두 구매하는 것이 최소 가격입니다. 하지만 패키지 가격이 낱개 6개의 가격보다 더 낮은 경우가 중요합니다. 어쨌든 필요한 기타 줄이 6개 이상이라면 그만큼은 무조건 패키지를 사는 것이 최소 가격일 겁니다. 하지만 패키지를 살 수 있는 만큼 모두 구매한 .. 2021. 4. 20. 이전 1 ··· 5 6 7 8 9 10 11 ··· 26 다음