본문 바로가기

프로그래밍/PS

 (80)
[C++] 백준 2580번: 스도쿠 문제 바로가기 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 개요 백준에서 단계별로 풀어보기를 쭉 이어나가다가 이 문제를 맞닥트렸다. 무려 골드4의 난이도를 자랑한다. 의외로 첫 풀이는 간단했다. 그냥 규칙을 적용했더니, 예제는 그냥 풀려버렸다. 그냥 빈 칸 마다 들어갈 수 있는 후보 하나를 쭉 대입하는 방식이었다. 하지만, 당연하게도 그건 답이 아니었다. 풀이 이 문제는 백트랙킹으로 분류된 만큼, 빈 칸에 들어갈 수의 후보가 하나가 아닐 수도 있다. 그래서 재귀함수를 구현했다. 기존 코드에서 큰 변화는 없..
[C++] 백준 16236번: 아기 상어 문제 바로가기 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 문제 NxN 크기의 공간에 물고기 M 마리와 아기 상어 1마리가 있다. 아기 상어의 처음 크기는 2이고, 1초에 한 칸씩 이동하며 물고기를 먹는 시간은 무시한다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있으며, 자기 크기만큼 물고기를 먹으면 크기가 1 커진다. 아기 상어의 이동방향 결정 방법은 아래와 같다. 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다. 먹을 수 있는 물고기가 1마리라면..
[C++] 백준 1107번: 리모컨 문제 바로가기 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 문제 수빈이는 악력이 지나치게 쎈가보다. 리모컨을 다루다가 일부 숫자 버튼이 고장났다. - 숫자 버튼이 고장났다는 내용을 문제 다 풀고 글 쓰는 지금 알았다. +, -도 고려하는 줄 알고 assert까지 써가봐 확인했는데... 역시 문제를 몇 번은 꼼꼼히 읽는 버릇을 들여야겠다. 0~9번까지의 숫자, +, - 버튼이 있다. 수빈이는 N번 채널로 이동하고 싶다. 어떤 버튼이 고장났는지 주어질 때, 채널 N으로 이동하려면 최소 몇 번 ..
[C++] 백준 10026번: 적록색약 문제 바로가기 문제 크기가 N×N인 그리드의 각 칸에 RGB 중 하나를 칠한 그림이 있다. 같은 색으로 이루어져 있는 구역으로 몇 개 나뉘어져 있다. 같은 색상이 상하좌우로 인접해 있으면 같은 구역에 속한다. 적록색약인 사람은 R과 G를 구별하지 못 한다. 그리드가 주어졌을 때, 적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역수를 세어보자. 조건 1 ≤ N ≤ 100 풀이 이 문제는 2667번의 응용버전이다. 그리드에서 RGB 문자가 있는 한 칸을 기준으로 너비우선탐색을 하는데, 한 번 방문한 칸에는 숫자 등을 채워 넣는다. 그리고 더 이상 RGB 문자가 등장하지 않을 때까지 이를 반복한 뒤, 몇 번을 반복했는지만 출력하면 그게 구역의 수이다. 이 문제에서는 이를 두 번..
[C++] 백준 15686번: 치킨 배달 문제 바로가기 ⛳문제⛳ 1. 크기가 N×N인 도시는 (r, c) 좌표에 1×1크기의 칸으로 구성돼 있고, r과 c는 1부터 시작한다. 2. 도시의 각 칸은 치킨집(2)과 빈칸(0), 집(1) 중 하나이며 각 숫자로 주어진다. 3. 치킨 거리란 어떤 집과 그 집에서 가장 가까운 치킨집 사이의 거리이며 거리는 각 좌표의 차이(절댓값) 합이다. 4. 도시의 치킨 거리는 도시 내 모든 집 각각의 치킨거리 합이다. 5. 도시의 치킨 집 중 M개 점포를 남기고 나머지는 폐업시키고자 한다. 6. 치킨집 중에서 최대 M개를 골라 도시의 치킨 거리가 최소가 됐을 때, 도시의 치킨 거리를 구해보자. 🧨입력조건🧨 2 ≤ N ≤ 50 1 ≤ M ≤ 13 ✨풀이✨ 1. 좌표 순서대로 입력을 받는다. 2. 입력된 수가 1 또는 ..
[C++] 백준 7569번: 토마토 문제 바로가기 🎊문제 개관🎊 이전에 풀었던 7576번과 유사하다. 하지만 그 때보다 한 차원 증가했다. 나는 오른쪽과 같은 좌표계를 사용할 것이다. // Vector3(h, r, c) typedef tuple Vector3; 🧨입력 조건🧨 2 ≤ N, M, H ≤ 100 🎢풀이🎢 📖 이전에 풀었던 7576번의 풀이를 많이 참고했다. 1. 토마토의 상태를 보여주는 3차원 배열 tomatos, 오늘 익은 토마토의 위치를 저장하는 큐 today, 내일 익을 토마토의 위치를 저장하는 큐 tomorrow가 있다. 2. 오늘 익은 토마토의 위치를 모두 한 번씩 방문하며 다음(3~5)을 반복한다. 3. 인접한 토마토(neighbor)가 아직 안 익었다면, 내일 익을 토마토에 위치를 저장해둔다. 4. 그 토마토의 상태..
[C++] 백준 17626번: Four Sqaures 문제 바로가기 ⚽문제가 무엇일까?⚽ 1 ≤ N ≤ 50,000인 자연수 N이 입력되면, 이 수를 제곱수의 합으로 나타낼 수 있다. 라그랑주는 모든 자연수를 4개 이하의 제곱수 합으로 표현할 수 있음을 증명했다. 어떤 자연수를 제곱수의 합으로 나타내는 여러가지일 수 있다. 우리는 주어진 자연수 N을 제곱수의 합으로 나타낼 때, 그 개수의 최소값을 찾는게 목표다. ⚾어떻게 풀지?⚾ 위 사진처럼 차근차근 적어봐도, 규칙성을 찾기란 어렵다. 그래서 단순하게 생각했다. N 이하의 제곱수 중 가장 큰 수부터 연산을 하는 것이다. 예로, N이 8이면 4 두 번으로 표현이 된다. 하지만, 이렇게 설계하고 예제를 돌려보면 다른 답이 나온다. 가장 큰 제곱수가 항상 옳은 선택은 아니라는 뜻이다. 따라서, 이를 상한선을 낮..
[C++] 백준 14500번: 테트로미노 문제 바로가기 ⛳문제에서 요구하는 것⛳ 1. 크기가 N×M인 종이 위에 테트로미노 하나를 놓는다. 2. 테트로미노가 놓인 칸에 쓰여있는 수들의 합의 최대값을 알아보자. 3. 테트로미노를 회전, 대칭을 시켜도 된다. 🧨주어진 조건🧨 1. 4 ≤ N, M ≤ 500 2. 각 칸의 입력은 1000 미만의 자연수다. ✨처음 생각한 풀이✨ 1. 각 점을 방문한다. 2. 다섯가지의 테트로미노에 대해, 3. 기준 위치를 방문한 점에 놓고 4. 90도씩 회전시키며 테트로미노가 놓인 칸에 쓰여있는 수의 합을 구한다. 5. 이번엔 좌우, 상하 대칭을 시켜서 확인한다. - 그런데, 테트로미노가 놓인 칸을 어떻게 알아내냐가 관건이다. - 나는 각 테트로미노의 기준 위치를 (0, 0)으로 두고, 그 테트로미노를 구성하는 다른 ..

티스토리툴바