펭로그

문제링크 : https://noj.am/11047 최소의 동전 갯수로 주어진 금액을 때려맞추는 그리디한 문제이다.주어진 동전도 이미 정렬되어있기 때문에 솔루션도 매우 간단하다.큰 동전부터 차례대로 나누어서 값을 누적시키고 나머지 값들은 더 작은 단위의 동전으로 나눠서 또 누적시키면 쉽게 구할 수 있다.혹시라도 중간에 모든 동전을 소진했을 경우 바로 탈출하기 위해 24번째 줄과 같이 total == 0일 경우 탈출하는 조건을 두었다. 123456789101112131415161718192021222324252627282930// BOJ_11047 동전 0#include using namespace std; int coins[11]; int main() { ios::sync_with_stdio(false);..

문제링크 : https://noj.am/2217 각 로프에는 동일한 하중이 걸려야 한다는 점이 이 문제의 핵심이다.이때, 각각의 로프에 걸리는 하중은 병렬로 연결되어 있는 어떤 로프의 최대 중량을 초과할 수는 없다.그렇기 때문에 현재 병렬로 연결되어있는 로프 중에서 가장 적은 수치의 최대 중량이 각 로프들에 걸릴 수 있는 최대 하중이 되는 것이다.따라서, 임의로 뽑은 로프들 중에서 가장 값이 작은 것을 뽑은 로프의 갯수 만큼 곱하면 답을 구할 수 있다. 각 로프의 최대 하중을 담은 배열을 내림차순으로 정렬하여 최대 하중 값이 큰 것부터 차례대로 계산을 해주고 그 중에서 최대치만을 답으로 출력하면 된다. 예를 들자면, [110, 70, 20, 5, 35, 40]의 배열이 있다면 이를 내림차순 정렬하여 [1..

문제링크 : https://programmers.co.kr/learn/courses/30/lessons/42576 algorithm 헤더의 sort를 사용하면 쉽게 풀 수 있다.정렬된 후 participant와 completion 배열을 비교하다가 서로 다른 부분을 발견하게 되면 완주하지 못한 선수가 빠진 것임을 알 수 있기 때문에 아래와 같이 간단한 코드를 작성할 수 있다. 예를 들어 아래와 같이 두 배열을 정렬했을때["abc", "abcd", "bcde", "cvfw"] - participant["abc", "abcd", "cvfw"] - completion "bcde"가 빠져있어서 2번 인덱스의 값이 서로 불일치하는 순간을 확인할 수 있다. 이때의 participant의 인덱스 값을 출력하면 정답이..

문제링크 : https://programmers.co.kr/learn/courses/30/lessons/42577 알고리즘 헤더에 있는 sort를 이용하여 쉽게 구현하였다.먼저 sort를 하게되면 숫자 순서대로 정렬이 되고 문제에서 요구하는 접두어의 경우 반드시 인접한 위치에 정렬되게 된다.예를 들어서 [12345, 332, 123]을 정렬하게 되면 [123, 12345, 332] 이런 식으로 정렬된다는 뜻이다.그리고 여기서 한가지 알 수 있는 사실은 정렬된 이후 접두어에 해당하는 숫자는 무조건 앞에 나오게 된다.따라서, 모든 배열의 원소를 완전탐색하여 현재의 위치와 현재의 위치 직전의 문자열을 서로 비교하여 string 클래스의 find() 함수를 사용하여 일치하는 문자열이 나오면 정답으로 출력하면 된..

문제링크 : https://noj.am/1475 문자열을 입력 받아서 갯수를 카운팅 하고 그 중에서 가장 많이 카운팅 된 숫자가 몇개인 지를 구하는 문제이다.단, 문제의 조건에서 6과 9는 뒤집어서 사용할 수도 있다고 했기 때문에 0.5씩 카운팅하여 쉽게 해결하였다.이러한 과정을 위해서 float형을 사용하였다. 12345678910111213141516171819202122232425262728293031323334353637383940414243// BOJ_1475 방 번호#include #include using namespace std; int max(int a, int b){ return a > b ? a : b;} int round(float input){ float temp = (int)in..

문제링크 : https://noj.am/1018 브루트포스 문제로 4중 for문이라는 더러운 코드로 문제를 풀게 되었다..... 체스판의 격자를 다음과 같은 2가지의 임의의 규칙을 정할 수 있다.1-1. 홀수번째 줄의 홀수 칸이 'W'1-2. 홀수번째 줄의 짝수 칸이 'B'1-3. 짝수번째 줄의 짝수 칸이 'W'1-4. 짝수번째 줄의 짝수 칸이 'B'or2-1. 홀수번째 줄의 홀수 칸이 'B'2-2. 홀수번째 줄의 짝수 칸이 'W'2-3. 짝수번째 줄의 짝수 칸이'B'2-4. 짝수번째 줄의 짝수 칸이'W' 위와 같은 조건에 해당이 되지 않는 칸이라면 전부 카운트를 시켜서 값을 누적시키면 다시 칠해야하는 칸이 몇칸인지 구할 수 있다.하지만 2가지의 case를 모두 비교할 필요 없이 1의 case를 골라서 ..

문제링크 : https://noj.am/5566 주사위의 지시사항 대로 구현하면 쉽게 풀리는 단순 시뮬레이션 문제이다.1. 현재 위치에서 주사위를 던져 해당 눈금만큼 진행한다.2. 보드의 범위를 초과 했는지 체크한다.3. 초과하지 않았으면 진행된 자리에 있는 지시사항을 수행한다.4. 보드의 범위를 초과 했는지 체크한다. 1234567891011121314151617181920212223242526272829303132333435363738394041// BOJ_5566 주사위 게임#include using namespace std; int direction[1001];int dice[1001]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout..

문제링크 : https://noj.am/1120 단순하게 두 문자열을 같은 길이 만큼만 비교하여 일치하지 않는 만큼의 문자가 몇개인지를 체크하여 최소값을 구하는 브루트포스 알고리즘적 방법으로 접근하였다. 1. A의 앞에 아무 알파벳이나 추가한다. 2. A의 뒤에 아무 알파벳이나 추가한다.이 두 조건을 최소값이 나오게 하려면 추가할 아무 알파벳을 B와 같게 만들면 되기 때문에 신경 안써도 되는 조건이다. 12345678910111213141516171819202122232425262728293031323334// BOJ_1120 문자열#include #include using namespace std; int min(int a, int b) { return a > b ? b : a;} int main() ..

문제링크 : https://noj.am/1057 문제의 조건에서 지민과 한수가 둘이 만나기 전까지는 무조건 이긴다고 하였다.따라서 문제에서 나온 조건대로 하면 '만약 서로 대결하지 않을 때는 -1을 출력한다.'은 절대로 나올 수 없기 때문에 무시해도 된다. 두 사람이 만날 수 있는 조건은 A와 B가 각각 2n-1과 2n 이어야 하는 조건이다.계산을 편하게 하기 위해서 그냥 A, B를 작은 순서대로 정렬하고 A가 홀수이고 A-B의 차가 1이면 정답으로 출력하도록 했다. 두 사람이 각 라운드에서 만나지 못한다면 div( ) 함수를 통하여 입력값을 절반으로 나누어주면서 정답을 찾아가면 된다.절반씩 계속 나누기 때문에 최악의 경우에도 O(logN)의 시간복잡도를 보일 것이다. 1234567891011121314..