본문 바로가기

백준85

[BOJ] 6716 : Collecting Beepers 문제 링크 6716번: Collecting Beepers (acmicpc.net) 6716번: Collecting Beepers Karel is a robot who lives in a rectangular coordinate system where each place is designated by a set of integer coordinates (x and y). Your job is to design a program that will help Karel pick up a number of beepers that are placed in her world. To do so www.acmicpc.net 백트래킹이라고 소개되어있어서 풀어본 문제지만 딱히 백트래킹으로 풀리는 문제가 아니라서 백트래킹 문.. 2022. 1. 19.

[BOJ] 2629 : 양팔저울 문제 링크 https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 풀이 백트래킹을 공부하다가 만난 문제다. 저울을 기준으로 생각했을 때 i번째 추를 처리하는 방법은 3가지가 있다. 1. 왼쪽에 놓는다 2. 오른쪽에 놓는다 3. 놓지 않는다 맨 처음 떠오른 아이디어가 이것이었으므로 이것을 기반으로 코드를 작성했다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 3.. 2022. 1. 19.

[BOJ] 2661: 좋은 수열 문제 링크 https://www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 풀이 예전에 누군가의 코드를 따라치면서 대충 이해만 하고 넘어갔던 문제다. 이번에 다시 백트래킹을 풀어보면서 제대로 풀어보기로 했다. 백트래킹으로 string에 숫자를 하나씩 붙여나가는 방식으로 코드를 작성했다. 처음에 depth 1인 str은 '1'로 시작하는 백트래킹 함수를 호출했다. 그 이유는 좋은 수열중 가장 작은 수 이므로 맨 앞자리는 1일 것이다. 매 함수마다 지금까지 만들어진 수열이 좋.. 2022. 1. 19.

[BOJ] 1799 : 비숍 문제 링크 https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 백트래킹에 관한 문제다. 풀이 처음 문제를 읽었을 때 왜 이게 골드1 난이도의 문제일까? 라는 의문이 들었다. 비숍이 들어갈 위치는 정해져있고 거기에 비숍이 1. 놓이거나 2. 안놓이거나 둘 중 하나다. 비숍이 놓일 수 있는 모든 위치를 벡터에 저장한 뒤 그 위치를 백트래킹으로 모두 돌면서 depth가 비숍이 놓일 수 있는 모든 칸의 개수와 같아지면 그때 체스판에 놓여있는 체스의 개수 중 최대값.. 2022. 1. 19.

이전 1 ··· 7 8 9 10 다음

티스토리툴바