본문 바로가기

백준172

[C++] 백준 14889번 : 스타트와 링크 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 문제 풀이 1. 능력치를 나타내는 2차원 배열 board에 값을 입력받고 팀원의 소속을 나타내는 배열 team을 초기화해준다. 2. 입력받은 총 인원 n의 반만큼 set_teams로 팀을 나누어주고 맞게 떨어진다면 함수 get_ability_of_team을 호출한다. 3. 함수 get_ability_of_team으로 나눠진 두 팀의 능력치를 연산하고, 뺀 값을 반환한다. 중복 없이 n의 반의 크기인 팀을 나누는 함수... 2021. 5. 26.
[C++] 백준 14888번 : 연산자 끼워넣기 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 문제 풀이 1. 피연산자와 연산자의 개수를 배열에 담는다. 2. 연산자를 끼워넣는 함수를 실행한다. 함수 getans는 변수 cnt(피연산자의 index)와 변수 result(연산 결과)를 매개변수로 가진다. 변수 cnt 가 n의 값과 일치하면 최대, 최소를 비교하여 값을 최신화한다. 피연산자의 순서는 고정이 되어있기 때문에 다음에 올 연산자.. 2021. 5. 26.
[C++] 백준 2580번 : 스도쿠 https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 문제 풀이 스도쿠의 특성상 전체 행, 열 그리고 9 분할된 3x3 박스 모두 값이 겹치지 않는지 확인해야 한다. 이 부분은 함수로 구현해서 따진다. 3x3 박스 영역은 입력받은 좌표를 3으로 나눈 값으로 따질 수 있다. 이후 1~9까지 값들을 빈 영역에다가 대입해보고 구현한 함수로 중복 여부를 따져본다. 중복이 없다면 다시 호출한다. 계속 값을 차례차례 확인하고 넘어가도 어떤 특정 좌표에서 어떤 .. 2021. 5. 24.
[C++] 백준 9663번 : N-Queen https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 풀이 같은 열, 행, 그리고 대각선에 위치하면 안 되기 때문에 함수로 위치할 수 있는지 체크한다. 좌표에 놓여있을 때, (A, B)와 (X, Y)가 같은 대각선 상에 위치한다면 A - X = B - Y이다. 그리고 col 배열의 값은 x 축, col 배열의 인덱스는 y축을 나타내는 점을 이용해서 배열에 값이 입력됐다면 해당 인덱스에 값이 위치할 수 있는지 여부를 함수로 체크하고 재귀 함수를 다시 불러온다. .. 2021. 5. 24.
[C++] 백준 17103번 : 골드바흐 파티션 https://www.acmicpc.net/problem/17103 17103번: 골드바흐 파티션 첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다. www.acmicpc.net 문제 풀이 에라토스테네스의 체를 이용해서 소수들을 정의하고 2부터 입력받은 값(N)의 반까지 경우를 모두 따진다. 느낀 점 예전의 소수 문제들과 비슷해서 바로 풀어봤는데 그 당시에는 시간제한이 널널해서 에라토스테네스의 체를 사용하지 않았는데 이번엔 0.5초 제한으로 안 쓸 수가 없었다. 이번 기회로 알고리즘을 다시 정리한 계기가 되었다. 에라토스테네스의 체 시간복잡도 : O(NloglogN) / 2.. 2021. 5. 24.
[C++] 백준 15652번 : N과 M (4) https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 풀이 N과 M(2) 번과 (3) 번을 섞은 듯한 문제이다. 재귀 호출을 할 때 이전 기준값을 시작점으로 삼으면 이전 배열 값보다 크거나 같은 값을 출력할 수 있다. 느낀 점 실은 이번 코드도 (2)번에서 한 것처럼 조건문으로 경우를 따져서 값을 대입하는 방식으로 했었다. 채점 이후 더 나은 방법이 없을까 고민하다가 (2) 번 문제처럼 시작점을 따지는 방법으로 넘어갔다. 코드 길이가 확연히 .. 2021. 5. 24.

티스토리툴바