https://www.acmicpc.net/problem/1487 1487번: 물건 팔기 첫째 줄에 최대 이익을 만들어주는 가격을 출력한다. 이익이 최대인 가격이 여러개라면, 가장 낮은 가격을 출력한다. 또, 어떤 가격으로 팔아도 이익을 남길 수 없다면 0을 출력한다. www.acmicpc.net 1. Logic n의 범위가 50이기 때문에 완탐을 돌려도 시간복잡도가 안넘는다! 먼저 입력을 받은 후 입력값을 오름차순으로 정렬한다. 그럼 작은 가격부터 기준을 잡고, 기준으로부터 배열끝까지 돌면서 가격을 계산한다. 모든 수를 다 돌게되면 시간복잡도도 넘을 뿐더러, 기준보다 작으면 선택받지 못하기 때문에 무조건 선택받을 수 있게 배열의 가격을 기준으로 잡는것이다. 가격의 기준을 잡는 부분이 첫번째 for문에 ..
백준
https://www.acmicpc.net/problem/2444 2444번: 별 찍기 - 7 첫째 줄부터 2×N-1번째 줄까지 차례대로 별을 출력한다. www.acmicpc.net 1. Logic 별찍기 구현! 2. Code #include using namespace std; int main() { int n; cin >> n; for(int i = n-1; i >= 0; i--) { for(int j = 0; j < i; j++) { cout
https://www.acmicpc.net/problem/2342 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net 1. Logic DDR에서 이전에 갔던 곳을 똑같은 경우의 수로 갈 수 있기 때문에 메모이제이션을 활용하여 풀이했다. 규칙이 직관적으로 보여서 topdown으로 풀이하기 쉬웠다. 밟고 있던 위치를 다시 밟을경우 +1 처음 시작점인 0의 위치에서 움직일 경우 +2 인접한 위치로 움직일 경우 +3 반대편으로 움직일 경우 +4 처음에는 모든 경우의 수를 다 세줘서 보기..
https://www.acmicpc.net/problem/1952 1952번: 달팽이2 M줄 N칸으로 되어 있는 표 위에, 달팽이 모양으로 선을 그리려고 한다. 위의 그림은 M=5, N=3의 예이다. 이제 표의 왼쪽 위 칸(ㅇ)에서 시작하여, 오른쪽으로 선을 그려 나간다. 표의 바깥 또는 이미 www.acmicpc.net 1. Logic 2차원 배열로 BFS를 돌려서 하는 방법도 있고 단순 규칙을 찾아서 풀이할 수도 있다. 2. Code 구현 풀이 #include using namespace std; int n, m; bool vis[101][101]; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; int main() { int n, m; cin >> n..
https://www.acmicpc.net/problem/20057 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 1. Logic 달팽이 탐색 부분은 2중 for문을 돌려서 확인하고 움직이는 칸수가 총 2번씩 반복된다는 규칙은 쉽게 찾았지만 저 좌표에 따라 비율 계산을 어떻게 해야하나 고민을 많이했고 아래의 블로그에서 광명을 찾아버렸다.. 댓글을 보니 나 말고도 여러 사람이 광명을 찾고 간듯..? 풀다가 막혀서 블로그를 찾아들어온 과거의 나 같은 사람들을 위해 아래에 블로그 링..
https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 1. Logic 기본 3차원 BFS 문제이다. Z축도 있기 때문에 6방향 탐색을 돌아주면 된다. 예외처리만 잘 해주면 무난히 통과하는 문제이다. 2. Code #include using namespace std; int l, r, c; int sx, sy, sz; char building[31][31][31]; bool vis[31][31][31]; int dz[6] = {0, 0, 0, 0, 1, -..
https://www.acmicpc.net/problem/15661 15661번: 링크와 스타트 첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100 www.acmicpc.net 1. Logic 팀을 꾸릴때 인원이 최대 20명이고 1명부터 팀을 꾸릴 수 있기 때문에 시간복잡도가 19!이 나온다. 이렇게 되면 시간복잡도를 한참 뛰어넘기 때문에 로직을 생각해 봐야 한다. 우리는 두 팀의 능력치의 절댓값을 판단해야 하기 때문에 1, 2, 3, 4의 인원으로 팀을 꾸리면 1,2 를 골라서 팀을 꾸리는 것과 3, 4를 골라서 팀을 꾸려서..
https://www.acmicpc.net/problem/2442 2442번: 별 찍기 - 5 첫째 줄에는 별 1개, 둘째 줄에는 별 3개, ..., N번째 줄에는 별 2×N-1개를 찍는 문제 별은 가운데를 기준으로 대칭이어야 한다. www.acmicpc.net 1. Logic 컴공과 1학년 C언어 과목 필수 과제이다ㅋㅋㅋㅋ n=5일때를 기준으로 보면 1번째 줄 : 공백 4 / 별 1 2번째 줄 : 공백 3 / 별 3 3번째 줄 : 공백 2 / 별 5 4번째 줄 : 공백 1 / 별 7 5번째 줄 : 공백 0 / 별 9 일반화 시켜보면 0부터 시작하는 i번째 줄을 기준으로 공백의 갯수는 n-i-1 별의 갯수는 1+i*2개이다. 이대로 for문을 작성하면 된다. 2. Code #include using na..
https://www.acmicpc.net/problem/1503 1503번: 세 수 고르기 첫째 줄에 N(1 ≤ N ≤ 1,000)과 집합 S의 크기 M(0 ≤ M ≤ 50)이 주어진다. 둘째 줄에는 집합 S에 들어있는 수가 주어진다. 집합에 들어있는 수는 1,000보다 작거나 같은 자연수이고, 공백으로 구분되어 www.acmicpc.net 1. Logic 일단 입력받은 집합에 있는 숫자를 제외해야하기 때문에 bool배열을 활용하여 제외해야 하는 숫자들을 걸러줬다. 그리고 N의 범위가 1000까지이기 때문에 브루트포싱을 돌려서 1~1001까지 3중 for문을 활용하여 풀이해줬다. 시간복잡도가 1000^3 만큼 나와서 안될 줄 알았는데 내부 테케가 부족했는지 통과됐다. 이게 왜돼? 2초에 2억번 연산이라..
https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 1. Logic 기본 BFS 문제이다. 최소 이동을 고르기 때문에 우선순위 큐를 활용해서 버튼을 누르는 횟수가 가장 작은것들을 먼저 빼줬고, if문으로 조건을 나눌 때 계속 OutOfBounds가 나와서 잠깐 막혔는데, if문에서 거를 때 조건 두개가 and연산으로 묶여있으면 앞에 조건을 먼저 탐색하기 때문에if문 조건 순서를 바꿔서 해결해줬다 if(cur-d >= 1 && !vis[cur-d]) 이 부분에서..
