본문 바로가기

전체 글

 (145)
[C++] 문제집 (1766번) 위상 정렬 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 문제풀이 위상정렬 문제 접근 방법을 기억하지 못해 정답을 참고했다. 이참에 위상정렬에 대해 다시 한번 공부해 보았다. 위상 정렬은 "사이클이 없는 다이렉션 그래프" 문제를 풀 때 사용한다. 즉 순서가 정해져 있고, 이 순서가 순환하지 않아야 한다. 위상정렬은 위와 같은 조건을 가진 그래프를 "진입차수"의 개수를 이용하여 순서대로 출력하도록 또는 동작하도록 할 수 있다..
[C++] 수열 (2491번) https://www.acmicpc.net/problem/2491 2491번: 수열 0에서부터 9까지의 숫자로 이루어진 N개의 숫자가 나열된 수열이 있다. 그 수열 안에서 연속해서 커지거나(같은 것 포함), 혹은 연속해서 작아지는(같은 것 포함) 수열 중 가장 길이가 긴 것을 찾 www.acmicpc.net 문제풀이 하나씩 뺴먹어 버려서 틀리는 경우가 생긴다.. 초기 answer값을 1로 두고, 반복문 마지막 마다 정답 값을 갱신하도록 해주었다. 처음 값만 따로 입력받아 before에 저장한뒤, 감소 증가 길이를 저장할 변수를 선언하고 반복문을 돌며 단조증가, 단조감소에 따라 갈이를 늘려주거나 다시 1로만들어주면 간단하게 구현이 가능하다. #include using namespace std; int ma..
[C++] 게리맨더링2 (17779번) https://www.acmicpc.net/problem/17779 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 www.acmicpc.net 문제풀이 개인적으로 상성이 너무 안맞는 문제다. 2차원 배열의 인덱스를 잘 조절하여 만복문을 돌리는건데 덧셈 뺄셈이 너무 헷갈려 죽는줄 알았다. 조건을 보면 사각형 모양의 테두리는 반드시 생겨야 한다. 시작지점 행 열을 0으로 두고 풀었다. 그러므로 열의 시작지점은 반드시 1부터 n-2 사이 이어야 한다. 행의 시작지점은 0부터 n-3까지 이어야 한다. 그래야 사각형이 만들어진다. 그리고 d1은 현재..
[C++] 낚시왕 (17143번) https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 문제풀이 골드 1치고 풀만한 문제라고 생각한다. 개인적으로 드래곤 커브 같은 문제들이 더 어려운것 같다. 두 부분으로 나누어 풀어주었다. 1. 낚시꾼이 오른쪽으로 이동해 상어를 낚시한다. 2. 상어가 이동한다. 상어를 저장하기 위해 구조체를 선언하여 사용하였다. 1번은 매우 쉽게 구현할 수 있다. 그냥 열 반복하면서 상어를 찾으면 정답에 크기만큼 더해주고 상어를 없애면 된다. ..
[C++] 나무 재테크 (16235번) 나무 재테크 https://www.acmicpc.net/problem/16235 시간 제한메모리 제한제출정답맞힌 사람정답 비율 0.3 초 (하단 참고) 512 MB 58288 14393 8032 22.064% 문제 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 떨어진 칸의 개수, c는 가장 왼쪽으로부터 떨어진 칸의 개수이다. r과 c는 1부터 시작한다. 상도는 전자통신공학과 출신답게 땅의 양분을 조사하는 로봇 S2D2를 만들었다. S2D2는 1×1 크기의 칸에 들어있는 양분을 조사해 상도에게 전송하고, 모든 칸에 대해서 조사를 한다. 가장 처음에 ..
[C++] 사다리 조작 (15684번) 사다리 조작 https://www.acmicpc.net/problem/15684 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 512 MB 64502 17211 8322 21.688% 문제 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선이 같은 위치를 갖는다. 아래 그림은 N = 5, H = 6 인 경우의 그림이고, 가로선은 없다. 초록선은 세로선을 나타내고, 초록선과 점선이 교차하는 점은 가로선을 놓을 수 있는 점이다. 가로선은 인접한 두 세로선을 연결해야 한다. 단, 두 가로선이 연속하거나 서로 접하면 안 된다. 또, 가로선은 점선 위에 있어야 한다. ..
[C++] 2048 (Easy) (12100번) 2048 (Easy) https://www.acmicpc.net/problem/12100 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 512 MB 82722 24108 14076 26.262% 문제 2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다. 이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다) 의 경우에서 위로 블록을 이..
[C++] 마법사 상어와 파이어볼 (20056번) 마법사 상어와 파이어볼 https://www.acmicpc.net/problem/20056 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 512 MB 19279 7771 4732 36.591% 문제 어른 상어가 마법사가 되었고, 파이어볼을 배웠다. 마법사 상어가 크기가 N×N인 격자에 파이어볼 M개를 발사했다. 가장 처음에 파이어볼은 각자 위치에서 이동을 대기하고 있다. i번 파이어볼의 위치는 (ri, ci), 질량은 mi이고, 방향은 di, 속력은 si이다. 위치 (r, c)는 r행 c열을 의미한다. 격자의 행과 열은 1번부터 N번까지 번호가 매겨져 있고, 1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다. 파이어볼의 방향은 어떤 칸과 인접한 8개의 칸의 방향을 의미하며, 정..

티스토리툴바