전체 글

1. 문제핵심종말의 날 까지 의 날짜가 몇 번째 날인 지 / 없다면 -1 출력종말의 날는 M과 N의 최소공배수M, N의 범위는 4만 이하이기 때문에 최악의 경우 4만*4만번 째 날이 종말의 날이 될 수 있다.day를 1씩 증가시키면서 확인하면 연산 횟수가 1억번을 초과하기 때문에 시간 제한에 걸려버린다.따라서 조건으로 주어지는 x 혹은 y를 고정값으로 두고 M 또는 N 만큼 day를 증가시켜 일치하는 날이 존재하는 지 확인한다.예를 들어, x를 시작일(=day)로 두고 day += m 씩 날짜를 건너뛰면서 그 날의 y'값이 조건의 y값과 일치하는 지 확인하면 된다. 2. 해결#include using namespace std;int t;int main(){ cin.tie(NULL); ios_b..

1. 문제핵심1번 칸부터 100번 칸까지 도달할 때 주사위를 최소 몇 번 굴려야 하는가1번 칸부터 주사위를 1~6씩 굴렸을 때 도달하는 칸의 cost를 계산해주면서 100번 칸까지 확장해나간다.이 때 x번 칸에 뱀 또는 사다리가 존재하고 이 경우 특정 칸으로 즉시 이동한다.bfs(너비 우선 탐색)으로 탐색하면서 cost를 갱신해 나가고 뱀/사다리가 존재하는 칸은 연결되는 칸에 cost를 계산하도록 한다. 2. 해결#include using namespace std;int n, m;int grid[104];int cost[104];bool visited[104];void bfs(){ queue q; q.push(1); visited[1] = true; while (!q.empty())..

1. 문제핵심100만 길이의 문자열을 한 번만 탐색해서 해결해야 한다.최소 단위인 IOI를 탐색하는 것이 핵심이다. 2. 해결#include using namespace std;int n, m;string input;int main(){ cin.tie(NULL); ios_base::sync_with_stdio(false); cin >> n >> m >> input; int idx = 0; int cnt = 0; int ans = 0; while (idx IOI가 n만큼 나오면 정답을 1씩 증가하는 로직에서 바로 뒤에 IOI가 추가로 나오는 경우를 고려하지 않아서 틀린 경우가 있었다.IOI가 나온 횟수인 cnt를 0으로 갱신하는 것이 아니라 -1만 해주면 바로 뒤에 I..

1. 문제핵심n개의 회의 일정이 주어진다. (시작시간, 종료시간)회의가 겹치지 않게 일정을 정렬할 때 최대 몇 개 회의일정을 정할 수 있을까일정을 잡는 규칙은 현재 회의 종료 시간 최대한 일정을 많이 잡기 위한 규칙 빨리 시작하고 빨리 끝나는 회의 먼저 일정을 잡는다. 2. 해결#include using namespace std;int n;vector> meetings;bool compare(pair a, pair b){ if (a.second == b.second) return a.first > n; while (n--) { int start, end; cin >> start >> end; meetings.push_back({start,..

1. 문제핵심NxN 맵이 주어지고 1이면 집, 2면 치킨집이다.M개의 치킨집을 고른 경우의 수마다 치킨 거리를 계산한다.그 경우의 수 중에서 최소값을 구한다. 2. 해결#include using namespace std;int N, M, ans = INT32_MAX;vector> house;vector> chicken;void combination(vector> v, int s){ if (v.size() == M) { int dist[104]; fill(&dist[0], &dist[0] + 104, INT32_MAX); for (int i = 0; i > N >> M; for (int i = 1; i > input; if (inpu..

⚓ 문제유저가 영역 밖에서 영역 안으로 들어왔을 때 흔적과 영역의 경계가 만드는 닫힌 경계을 추출한다.정점 정보를 가지고 평면을 생성한다.⚓ 접근1. 흔적과 영역의 경계가 만드는 닫힌 경계영역 밖으로 나갔을 때/들어왔을 때는 bool flag를 통해 판별한다.Creature의 현재 밟고 있는 위치가 Area 오브젝트가 아닐 때 흔적 좌표를 List에 저장하기 시작한다.다시 영역 안으로 들어왔을 때 흔적과 기존 영역의 경계가 이루는 폐구간을 새로운 영역의 경계로 정의한다.이 때, 새로운 영역은 이루는 정점들은 시계방향으로 나열된 List여야 한다.(Mesh 정점, 삼각형 규칙 때문)Creature가 흔적을 남기는 방향은 2가지 경우가 있다. a) 시계방향 b) 반시계방향a) 시계방향의 경우 흔적 배열의 처..

⚓문제paper.io 2에서는 유저가 맵 위를 이동한 궤적을 고유의 색으로 흔적으로 남기는 요소가 있다.그리고 이 흔적에 다른 유저 또는 자기 자신이 닿을 경우 흔적의 주인은 파괴된다.⚓접근1. 고유의 색으로 흔적으로 남기는 요소단색뿐만 아니라 이미지가 흔적에 그려질 수 있기 때문에 텍스처를 넣을 수 있는 컴포넌트를 사용객체의 매프레임 이동에 따라 부드러운 선을 그려야 하기 때문에 LineRenderer 사용한다.(좀 더 화려한 옵션을 위해서 파티클도 고려할 수 있겠지만 빠른 구현을 위해 LineRenderer로 진행)2. 흔적에 닿을 때 흔적의 주인이 파괴2.1) 방법 1(폐기)유저가 밟고 있는 현재 위치가 점유된 좌표인지 점유되지 않은 좌표인지 확인하는 법이 관건이다.유저들은 모두 동일한 맵 위를 이..

⚓문제Creature 객체가 맵 위에 남기는 흔적의 픽셀이 연속되지 않는다.uv 좌표상 (0, 0) -> (0, 1) 이 아니라 (0, 2) 같은 형식으로 건너뛰는 상황따라서, (0, 1)에 공백이 생기기 때문에 흔적을 밟았을 때 파괴되는 로직이 실행되지 않을 수 있다.⚓접근Creature는 자신의 위치와 매칭되는 맵의 uv 좌표에 자신의 데이터로 흔적을 남긴다.(예.픽셀 색깔)Creature는 Update()에서 매 프레임마다 자신의 위치를 갱신한다.Update()는 불규칙한 프레임으로 작동. FixedUpdate()는 일정한 간격으로 호출.두 Update() 함수 모두 프레임 사이에 Creature 객체가 이동하기 때문에 speed가 빠르다면 공백도 커지게 된다. transform.position +..

1. 문제핵심최대 100만 개의 수가 주어진다.index 기준으로 오른쪽에 있는 자신보다 큰 수 중 가장 가까운 수를 찾는다.없을 경우, -1을 index 위치에 넣는다.최대 100만 개가 주어지기 때문에 매번 오른쪽 수들을 탐색하는 방법은 안 된다. 2. 해결#include using namespace std;int N;int nums[1000004];int ans[1000004];stack st;int main(){ cin.tie(NULL); ios_base::sync_with_stdio(false); cin >> N; fill(&ans[0], &ans[N], -1); for (int i = 0; i > nums[i]; while (!st.empty() && n..

1. 문제핵심최대 1만 개의 노드가 주어지고 노드의 관계는 최대 10만 개가 데이터로 주어진다.각 노드와 연결된 노드들을 센 후 최대 개수인 노드를 출력한다.최대 개수인 노드가 여러 개일 경우 오름차순으로 출력한다.시간 제한은 5초모든 연결된 노드의 개수를 셀 경우 최대 1만*1만 = 1억 번 연산을 해야한다.1억 번 이하의 경우 충분히 감당할 수 있는 횟수기 때문에 dfs를 사용한다. 2. 해결#include using namespace std;int N, M;vector arr[10004];int dp[10004];bool visited[10004];int dfs(int x){ int ret = 1; visited[x] = true; if (arr[x].size() == 0) ..