프로그래밍 diary

12865번 - 평범한 배낭 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net dp 1 2 3 4 5 6 7 1 0 0 0 0 0 13 13 2 0 0 0 8 8 13 13 3 0 0 6 8 8 13 14 4 0 0 6 8 12 13 14 -> dp[N][K] dp[2][6]은 dp[1][6]와 dp[1][2] + 8을 비교하여 더 큰 값을 가져온 것이다. 여기서 2라는 인덱스 값..

11651번 - 좌표 정렬하기 2 입력받은 N에 따라 N개의 x, y좌표를 입력받기 위해 vetcor와 pair를 사용하였습니다. 입력받은 좌표를 문제 조건에 맞게 정렬하기 위해 sort를 사용하였습니다. sort()의 세 번째 인자에는 정렬의 기준이 되는 compare 함수(bool타입)를 입력하였습니다. compare 함수는 y좌표 값이 동일할 경우 x좌표 값을 비교하여 오름차순으로 정렬하고 동일하지 않을 경우 마찬가지로 오름차순으로 정렬하도록 구현하였습니다. #include #include #include using namespace std; bool compare(pairx, pairy) { if (x.second == y.second) return x.first < y.first; return ..

2292번 - 벌집 변수 cnt는 방의 번호, 변수 end는 cnt번방에 들어갈 수 있는 최대 숫자가 대입된다. 변수 num은 end의 범위를 증가시키기 위함이다. end를 1로 초기화(N==1 경우 무조건 1번 방이기 때문)하고, for문을 통해 end에 (6 * i)를 더해준다. 입력받은 N이 end를 넘지 않을 경우 cnt = 1 + i를 통해 방 번호를 저장하고 반복문을 종료한다. 입력받은 N이 end보다 클 경우 num += 2를 통해 end의 범위를 증가시킨다. 1번 방 : 1 (end1 = 1 + 6 * 0 = 1) 2번 방 : 2 ~ 7 (end2 = end1 + 6 * 1 = 7) 3번 방 : 8 ~ 19 (end3 = end2 + 6 * 2 = 19) 4번 방 : 20 ~ 37 (end..

1065번 - 한수 입력받은 N이 100보다 작을 경우(한 자릿수, 두 자릿수) 모두 등차수열을 만족하기 때문에 N을 출력 N이 100보다 크거나 같을 경우 한수의 개수를 99부터 시작하고 등차수열을 만족하는 경우 한수의 개수를 하나씩 증가시킴 등차수열인지 구분하는 과정에서 N을 string 타입으로 변환하여 십의 자릿수에서 일의 자릿수를 뺀 값과 백의 자릿수에서 십의 자릿수를 뺀 값이 일치할 경우 한수의 개수를 1씩 증가시킴 N이 1000일 경우 일의 자릿수, 십의 자릿수, 백의 자릿수만 비교해도 등차수열을 만족하지 않기에 고려하지 않아도 됨 #include #include using namespace std; int main() { int N, cnt = 0; cin >> N; string str; ..

4344번 - 평균은 넘겠지 테스트 케이스 수와 학생 수를 입력받고 for문을 사용하여 학생 점수 입력받기 vector를 사용하여 학생 수만큼 각각의 점수 입력받기 평균을 구해서 평균을 넘는 학생 수를 확인 평균을 넘는 학생 수를 전체 학생 수로 나눠 비율 확인 평균을 넘는 학생 수의 비율을 소수점 셋째 자리까지 출력 #include #include using namespace std; int main() { int C; //테스트 케이스 수 cin >> C; int num, sum = 0, avg, cnt = 0; for (int i = 0; i > num; //학생 수 vector v(num); for (int j = 0; j > v[j..

4949번 - 균형 잡힌 세상 string 타입으로 문자열 선언 while문을 사용하여 "."이 입력될 경우를 반복문 탈출 valance 함수를 구현하여 ()와 []가 짝이 맞을 경우와 맞기 않을 경우를 체크하여 빈 스택인지 아닌지를 반환 빈 스택일 경우 yes를 출력하고, 빈 스택이 아닐 경우 no를 출력함. #include #include #include using namespace std; int valance(string exp) { int len = exp.length(); stack v; for (int i = 0; i < len; i++) { if (exp[i] == '(' || exp[i] == '[') { v.push(exp[i]); } else if (exp[i] == ')') { if..

2161번 - 카드1 구조체 Node 선언 (입력받은 데이터: data, 노드 사이를 연결: next) 구조체 포인터 변수 선언(head, tail, cur, newNode) 동적 할당을 통해 노드 생성 노드에 데이터를 저장 (첫 번째 담긴 데이터일 경우 다음 연결은 NULL) if-else문을 사용하여 head가 NULL일 경우에는 newNode를 head에 저장하고, 아닐 경우 tail의 next노드에 newNode를 저장 주어진 데이터를 노드에 저장하고 모두 연결이 끝났다면 문제의 조건에 맞게 코드를 생성(while문 참고) [C언어] #include #include typedef struct _node { int data; struct _node* next; } Node; int main() { ..

2839번 - 설탕 배달 설탕 무게 입력받기 cnt_x, cnt_y 변수를 선언하여, cnt_x에는 설탕 무게를 5로 나눈 몫을 대입 while 반복문을 사용하여 봉지의 최소 개수 구하기 #include using namespace std; int main() { int N; cin >> N; int cnt_x = N / 5; int cnt_y; while (1) { if (cnt_x < 0) { cout

9095번 - 1, 2, 3 더하기 하나씩 경우의 수를 찾기에는 n이 10일 때 274개의 경우의 수를 찾아야 하기에 규칙을 찾는 방법을 택했습니다. n = 1일 때, 1가지 방법 존재 (1) n = 2일 때, 2가지 방법 존재 (1+1, 2) n = 3일 때, 4가지 방법 존재 (1+1+1, 1+2, 2+1, 3) n = 4일 때, 7가지 방법 존재 (1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 3+1, 1+3) 이쯤 되면 하나의 규칙이 보입니다. n-1의 방법, n-2의 방법, n-3의 방법의 합이 n이 4일 때 방법의 수라는 것을 알 수 있습니다. 하나 더 해보겠습니다. n = 5일 때, 13가지 방법 존재 (1+1+1+1+1, 1+1+1+2, 1+1+2+1, 1+2+1+1, 2+..

1152번 - 단어의 개수 * 문장이 공백으로 시작하든 공백으로 끝나든 상관없이 단어의 개수만 세는 게 중요함. 방법 1. vector사용 메인 함수와 split함수(vector타입의 함수)로 나눠서 구현 * split함수 매개 변수로 입력받은 문자열(input)과 단어 사이를 구분해줄 문자(part)를 사용한다. stringstream은 공백과 '\n'을 제외하고 자료형에 맞는 문자열을 빼오는 역할을 한다. 공백에 따라 분리된 ss를 tmp에 대입하고, tmp를 result에 붙여 넣는 과정을 반복한다. 완성된 result를 리턴한다. * main 함수 string 타입으로 문자열을 입력받는다. split함수를 호출하여 결과를 output 배열에 저장한다. for문을 사용하여 해당 output 배열에 ..