PS

문제 설명전체 스테이지의 개수 N, 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열 stages가 매개변수로 주어질 때, 실패율이 높은 스테이지부터 내림차순으로 스테이지 번호가 담겨 있는 배열을 return 하도록 구현하는 문제이다.(실패율) = (스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수) / (스테이지에 도달한 플레이어 수)주요 로직1. 정렬 알고리즘 사용시간 복잡도가 O(NlogN)인 sort() 메서드를 사용하였다. cmp라는 비교함수를 매개 변수로 넣어 pair 에 대한 내림차순으로 정렬할 수 있도록 하였다. 2. 예외 생각히기원래는 아래와 같이 코드를 작성했었는데 5개의 TC에 대해서 실패가 떴다. 알고보니 num 값이 0이 되는 경우를 배제하여서 Divide..

https://www.acmicpc.net/problem/13567  문제 설명(0,0)에서 동쪽을 향해 서있는 상태에서 n개의 명령어가 들어온다,TURN 0 : 왼쪽으로 90도 회전TURN 1 : 오른쪽으로 90도 회전MOVE d : d만큼 이동n개의 명령어를 다 수행한 후에 좌표를 출력하면 된다. 만일 m*m 격자판을 벗어난다면 -1을 출력한다 주요 로직1. 단순 구현이다주의할 점은 왼쪽 상단이 (0,0)이 아니라는 왼쪽 하단이 (0,0)이라는 점이다 정답 코드#include using namespace std;string str;bool flag = true;int m,n,y,x,k,d,ans=-1;int dy[4] = {-1,0,1,0}, dx[4] = {0,1,0,-1};bool check(in..

https://www.acmicpc.net/problem/2096문제 설명n개의 줄에 세 개의 숫자가 주어진다. (i,j)가 이동할 수 있는 경로는 (i+1,j-1) 또는 (i+1,j) 또는 (i+1,j+1)로만 가능하다. 첫 줄에서부터 마지막 줄로 이동할 때 얻을 수 있는 최대 점수와 최저 점수를 구하는 문제이 주요 로직1. dp문제이다2. 메모리가 4MB이기 때문에 모든 입력을 다 받고 나서 계산하는 것보다는 입력값 한줄을 받고 나서 그 때 그때 계산해야 한다. 정답 코드#include using namespace std;int n,tmp1, tmp2;int input[4], mn[4], mx[4];int main(){ ios_base::sync_with_stdio(false); cin.tie(NUL..

https://www.acmicpc.net/problem/9095 문제 설명t개의 테스트 케이스가 주어진다.각 테스트 케이스마다 n이 주어지는데 이때 1,2,3을 가지고 n을 만들 수 있는 경우의 수를 출력하면 된다 주요 로직1. 점화식 찾기 (dp[i] = dp[i-1] + dp[i-2] + dp[i-3]) 정답 코드#include using namespace std;int t,n;int arr[15];int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; arr[1] = 1, arr[2] = 2, arr[3] = 4; for(int i=4; i> n; cout

https://www.acmicpc.net/problem/10026문제 설명n*n 크기의 배열이 주어진다.각 배열의 칸에는 R,G,B 중 하나의 값이 들어가 있는데, 적록 색약인 경우에는 R과 G를 구분하지 못해 한 색으로 본다. 가로 세로로 연결된 같은 색끼리 모여있는 것들이 적록색약과 적록색약이 아닌 사람이 봤을때 몇개인지 개수를 출력하는 문제이다. 주요 로직1. 그래프 탐색 문제이다dfs로 같은 색이면 계속해서 탐색하도록 코드를 구성했다 정답 코드#include using namespace std;int n;string str;int dy[4] = {-1,0,1,0}, dx[4] = {0,1,0,-1};int arr[104][104], brr[104][104], visited[104][104];vo..

https://www.acmicpc.net/problem/4963 문제 설명각 테스트 케이스마다 w와 h가 주어진다. w * h 크기의 배열이 주어지는데, 1은 땅을, 0은 바다를 의미한다.땅은 가로, 세로, 대각선으로 움직일 수 있다. 각 테스트 케이스별로 연결된 땅의 개수를 구하는 문제이다.마지막 테스트 케이스이라면 w와 h값으로 0이 주어진다  주요 로직1. 그래프 탐색 문제이다각 테스트 케이스마다 visited배열을 0으로 초기화하고 깊이 우선 탐색으로 배열을 탐색한다 정답 코드#include using namespace std;int w,h, arr[55][55], visited[55][55];int dy[8] = {-1,-1,0,1,1,1,0,-1}, dx[8] = {0,1,1,1,0,-1,-..

https://www.acmicpc.net/problem/2230 문제 설명n개의 정수로 이루어진 수열이 주어진다.이 수열 중 두 수를 골랐을 때 그 차이가 M이상이면서 제일 작은 경우를 구하는 문제이다.  주요 로직1. 투 포인터수열을 정렬한 다음에 i와 j를 선언해 탐색하면서 최적의 값을 찾아 낸다 2. 최솟값 설정 - 1,000,000,000  정답 코드#include using namespace std;int n,m,x;vector v;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n >> m; for(int i=0; i> x; v.push_back(x); } sort(v.begin(), v..

https://www.acmicpc.net/problem/2661 문제 설명좋은 수열이란 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 없는 수열을 뜻한다.예를 들어 33, 32121323 은 나쁜 수열이고 32, 32123은 좋은 수열이다.길이가 n인 좋은 수열들을 찾아 그 중 가장 작은 수를 출력한다 주요 로직1. 백트래킹1,2,3 중 숫자 하나씩을 추가하면서 현 상황에서 좋은 수열인지 확인을 하고 아니라면 stop, 맞다면 계속 탐색한다. 2. n의 범위처음에 go(int num, int size)로 num을 string이 아닌 int로 설정했었다. n의 범위가 80이하이기 때문에 80자리의 수까지 탐색할 수 있어야 하는 데 int는 약 20억 범위이기에 10자리까지만 탐색할 수 있다. 그..

https://www.acmicpc.net/problem/11660 문제 설명2차원 배열이 주어졌을 때, (y1,x1)부터 (y2,x2)까지의 합을 구하는 문제이다. 주요 로직1. 누적합을 사용하는 것이다.n의 범위가 1024까지이기에 이중 for문을 사용해서 문제를 풀면 시간 초과가 발생한다 i행 j열의 누적합 구하기pfix[i][j]는 1행부터 i행까지, 1열부터 j열까지의 모든 수의 합을 구한 값이다.pfix[i][j] = pfix[i-1][j] + pfix[i][j-1] - pfix[i-1][j-1] + arr[i][j]; (y1,x1)부터 (y2,x2)까지의 합 구하기pfix[y2][x2] - pfix[y1-1][x2] - pfix[y2][x1-1] + pfix[y1-1][x1-1] 정답 코드#..

https://www.acmicpc.net/problem/14889  문제 설명n x n 배열이 주어졌을 때, 두 팀으로 나누어서 두 팀간의 능력치 차가 최소가 되는 경우를 출력하는 문제이다.i번째와 j번째가 같은 팀이 되었을 때 능력치는 S(i,j) + S(j,i)이다. 주요 로직1. 비트 마스킹이다.-> 두 팀을 나누는 모든 경우의 수를 따져야 하므로 비트마스킹으로 경우마다 두 팀의 인원이 같은지 확인하고 능력치를 구하면 된다. 정답 코드#include using namespace std;int n,ret=987654321,arr[24][24];int check(vector v){ int sum = 0; for(int i=0; i> n; for(int i=0; i> arr[i][j]; } } fo..