록키의 No Pain, No Gain

https://www.acmicpc.net/problem/1238 1238번: 파티 문제 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 www.acmicpc.net 다익스트라 문제.. 이 문제를 이전에는 인접 행렬로 풀었었는데 N = 1000이기 때문에 인접 행렬은 총 1,000,000개의 int 변수가 필요하다. 하지만 총 간선의 개수가 10000개 이하로 정해져있기 때문에 인접 행렬보다는 인접 리스트가 메모리상 효율적이고 시간복잡도 상에서도 더욱 효율적이다. 좀 더 최적화적인 관점에서 문제를 바라볼 필요가 있겠다. 그리고, C++은 기본적으로 우선순..

https://www.acmicpc.net/problem/1238 1238번: 파티 문제 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 www.acmicpc.net 플로이드 워셜이나 다익스트라 알고리즘을 사용하면 되는 문제 중요한건 다익스트라를 거꾸로 오는 경로로 생각했어야 했다. 그렇지 않으면 시간초과난다!!!!! #include #include #include #include #include #define INF 1000000 using namespace std; int N, M, X; int adj[1001][1001]; priority_queue..

https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 시뮬레이션 문제 문제를 잘 읽고 이를 시각화 시키는 연습이 필요할 것 같다. 조급해 하지 말고 문제 집중해서 제대로 읽기 #include #include #include using namespace std; int N, M, K; int A[11][11]; int map[11][11]; vector tree[11][11]; int dx[] = { -1,-1,-1,0,0,1,1,1 ..

조합, 우선순위 큐를 사용하여 풀었다. 주의해야 할 점은 조합을 구할 때 기저 값 넘겨주는 것 그리고 정확하게 진행되는 상황을 종이에 써서 명확히 이해하고 코딩할것 !!!!!!!!!!!!! #include #include #include #include #include #include using namespace std; int T, N, answer; vector peoples; vector stairs; vector dist[2]; vector stairVal; void solution(int selected) { priority_queue pq[2]; for (int i = 0; i < peoples.size(); i++) { if (selected & (1 = 3) continue; count++..

https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 문제 1번부터 N번까지 번호가 매겨진 N개의 구역이 있다. 구역을 두 개의 선거구로 나누고, 각 구역은 두 선거구 중 하나에 포함되어야 한다. 선거구는 구역을 적어도 하나 포함해야 하고, 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다. 공평하게 선거구를 나누기 위해 두 선거구에 포함된 인구의 차이를 최소로 하려고 한다. 인구 차이의 최솟값을 구해보자 풀이 비트마스킹을 이용한 부분집합 + BFS를 이용하여..

https://www.acmicpc.net/problem/17822 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀있고, i번째 원판에 적힌 j번째 수의 위치는 (i, j)로 표현한다. 수의 위치는 다음을 만족한다. (i, 1)은 (i, 2), (i, M)과 인접하다. (i, M)은 (i, M-1), (i, 1)과 인접하다. (i, j)는 (i, j-1), (i, j www.acmicpc.net 작년 하반기 삼성 기출문제 주사위 윷놀이와 같이 나온 문제로 알고 있는데, 이것도 2달 전에 풀었는데 반례를 찾지 못해서 방치했다..

https://www.acmicpc.net/problem/17825 17825번: 주사위 윷놀이 첫째 줄에 주사위에서 나올 수 10개가 순서대로 주어진다. www.acmicpc.net 작년 삼성 하반기 기출문제 2달 전쯤에 풀었는데, 그 때 예외케이스를 찾지 못해서 못 푼 상태로 끝났었다. 그 상태로 방치해뒀다가 이번에 아예 새로 풀었는데 한번에 통과했다. 그 전에 고민 많이 했던 문제라 문제에 대한 분석이 확실 했던 듯 하다. 원래 알던 문제라 문제를 읽는 과정, 주의해야 할 부분에서 얻어갈 것은 별로 없었고 그냥 구현력만 좀 향상시킬 수 있었다.. 문제 말이 4개 있고, 1~5까지 있는 주사위를 던져서 나올 수 10개를 미리 알고 있을 떄, 얻을 수 있는 최댓값 구하기 풀이 그냥 중복순열 그리고 시뮬..

https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다. 연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 www.acmicpc.net 이 문제는 작년 상반기 삼성전자 인턴때 풀었던 것으로 기억나는 데, 그 때 바이러스가 이미 있는 부분에 대해서 시간을 체크해서 그거..