Jonyo Programming

[BOJ 1062(G4)리뷰] 처음에 문제 이해를 잘못해서 푸는데 시간을 오래 썼다. 문제의 조건을 보면 모든 단어는 "anta"로 시작되고 "tica"로 끝난다고 하였으니 K개의 글자에는 최소 "a,n,t,i,c"의 알파벳이 필요하다. 즉, K가 5미만 이라면 단 한개의 단어도 읽을 수 없다. 이 조건을 생각하며 나머지 알파벳에 대하여 완전탐색을 실시하면 된다. 이미 사용한 알파벳에 대하여 방문처리를 하고 남은 알파벳에 대해 완전탐색을 수행해 알파벳의 개수가 K개가 되었을때 읽을 수 있는 단어를 카운팅하고 최대값을 계산해주면 된다. 문제를 이해하고 나면 전형적인 백트래킹 문제로 바뀌게 된다. 그리고 알파벳을 체크하는 배열은 ASCII코드 값을 이용하여 관리하면 편하다. /* 21.01.11 BOJ : ..

[BOJ 2529(S2) 리뷰] 오랜만에 백트래킹 카테고리에서 문제를 풀었다. 실버문제라 그런지 쉽게 구현을 떠올릴 수 있었다. 전형적인 백트래킹 방법을 통해서 부등호 조건에 맞지 않는 경우 가지치기를 하면 된다. 다만 출력할때 021 이런식으로 맨 앞자리에 0이 오는경우가 있으므로 문자열로 출력해야 한다. 이때 어떻게 할까 고민을하다 그냥 string객체에 max,min함수를 써봤는데 잘 동작했다. #include #include #include #include using namespace std; char ans[10]; string ansmin("987654321"); string ansmax("0"); vector sign; bool isUsed[10]; int k; void go(int n) {..

[BOJ 17142(G4) 리뷰] 지난 연구소, 연구소 2 문제에 이어 다른버전의 문제이다. 근데 연구소 2 문제와 코드 한줄차이라 올릴까 말까 고민했다. 문제 설명을 잘 보면 지난 연구소 2와 동일한 조건인데, 기존에 바이러스였던 위치는 새로 바이러스가 퍼지는것이 아니므로 퍼지는 시간을 계산할때 포함시키지 않는다는 소리다. 그렇기에 아래처럼 방문한 곳이 기존의 바이러스 위치라면 거리값을 return 할때 포함하지 않도록 했다. 너무 간단해서 뭔가 놓친게 있나 싶어 문제를 다시 읽어봤는데 별 다른 문제점을 못찾길래 제출했더니 정답이 나왔다. (솔직히 정답나올지 몰랐음 이왜맞??..) #include #include #include #include #include using namespace std; #d..

[BOJ 17141(G5) 리뷰] 지난번 풀었던 연구소 문제의 다른 버전이다. 저번엔 백트래킹으로 풀었지만 이번엔 next_permutation 함수를 이용했다. 지난번에는 벽을 세워 바이러스를 막아야했다면 이번엔 바이러스를 퍼지게할 위치를 고른다음 가장 빨리 바이러스가 퍼지는 위치에서 바이러스가 퍼지는 시간의 최소값을 출력해야한다. 그냥 주어진 시뮬레이션대로 구현하면 되는거라 별도의 디버깅없이 한번에 구현하고 바로 정답처리가 되었다. 1.먼저 next_permutation함수를 이용해서 총 K개의 바이러스 중 M개의 바이러스를 선택하여 벡터에 담는다. 2.선택된 바이러스의 좌표값을 기준으로 BFS를 수행하여 최대 DIST배열을 통해 최대 거리를 측정한다. 3.바이러스가 끝까지 퍼지지 않았다면 그 값은 ..

[BOJ 14502(G5) 리뷰] 연구소에 벽을 3개 설치할 수 있다. 벽을 설치한 후에 연구실에 있는 바이러스는 빈 공간으로 퍼져 나간다. 벽으로 막혀있다면 더 이상 퍼져나가지 않는다. 연구소에 벽을 3개 설치하는 경우 중에서 가장 적게 바이러스가 퍼질때 바이러스가 퍼지지않는 칸의 개수를 구하는 문제이다. 백트래킹+BFS로 문제를 해결했다. 먼저 벽을 3개 세우는 경우를 백트래킹을 통해 하나씩 확인해주고, 각각의 경우에 대해 BFS를 수행하여 바이러스가 퍼지게 한 다음 바이러스가 퍼지지 않는 공간의 갯수를 세면 된다. 시간초과를 걱정하며 문제를 풀었는데 채점TC가 느슨해서인지 정답은 나왔지만 예제에 나온 테스트케이스는 제시간에 답이 안나왔다. 조합을 사용하여 최대한 속도를 줄였지만 그래도 맵은 크고 초..

사무실의 크기와 상태, 그리고 CCTV의 정보가 주어졌을 때, CCTV의 방향을 적절히 정해서, 사각 지대의 최소 크기를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 사무실의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 8) 둘째 줄부터 N개의 줄에는 사무실 각 칸의 정보가 주어진다. 0은 빈 칸, 6은 벽, 1~5는 CCTV를 나타내고, 문제에서 설명한 CCTV의 종류이다. CCTV의 최대 개수는 8개를 넘지 않는다. 출력 첫째 줄에 사각 지대의 최소 크기를 출력한다. [BOJ 15683 (G5) 리뷰] 문제가 드럽게 길다..; 그런데 문제가 길다는것은 그만큼 설명을 자세하게 해준다는것. 정확히 뭘 구현해야하는지 제시해주고 있다. 사각지대의 최소 크기를 구해야하므로 백트래킹을 이용..

입력 첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)이 주어진다. 둘째 줄부터 N개의 줄에는 도시의 정보가 주어진다. 도시의 정보는 0, 1, 2로 이루어져 있고, 0은 빈 칸, 1은 집, 2는 치킨집을 의미한다. 집의 개수는 2N개를 넘지 않으며, 적어도 1개는 존재한다. 치킨집의 개수는 M보다 크거나 같고, 13보다 작거나 같다. 출력 첫째 줄에 폐업시키지 않을 치킨집을 최대 M개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력한다. [BOJ 15686 (G5) 리뷰] 처음에 문제 이해가 잘 안돼서 여러번 읽었다. 집과 치킨집과의 거리를 치킨거리라고 하는데 주어진 치킨집의 개수를 만족하며 존재하는 집의 치킨거리의 합이 최소가 되는경우를 구하면 된다. 모든경우를 탐색해야하므로 백트래킹을 ..

[BOJ 1987(G4) 리뷰] 후... 엄청나게 힘들었던 문제다. 처음엔 문제 잘못읽고 BFS로 접근했다. 코딩 다했는데 그제서야 문제 제대로 이해하고 싹 갈아엎었다. 처음엔 set을 통해 문자를 하나하나씩 쌓으면서 중복된게 있는지 비교했는데, 처음에 백트래킹하면서 쌓아놓았던 문자를 제거하지 않아서 틀렸다. 이걸 수정하고 제출했더니 set때문인지 시간초과가 나왔다. 그래서 인터넷을 참고해 중복된걸 확인하는것을 A~Z까지 배열에 담아 O(1)로 확인했더니 통과되었다. 후.. 2시간은 넘게 걸린거같다. #include #include #include #include using namespace std; char board[21][21]; bool isUsed[21][21]; int dx[4] = { 1,-..